Wrong Doing

on
 
  1. // String (double) hash.
  2. // - call precal() with maximum length possible.
  3. // - init(s) calculates h[] values for s
  4. // - hashval(l, r) for hash of s[l...r]
  5.  
  6. const int N = 1e5 + 7;
  7. const ll P1 = 1e8 + 5e4 + 1;
  8. const ll P2 = 1e9 + 87;
  9. const ll MOD1 = 1e9 + 7;
  10. const ll MOD2 = 1e9 + 9;
  11.  
  12. ll pow1[N], pow2[N];
  13. ll h1[N], h2[N];
  14.  
  15. void precal(int n) {
  16.     pow1[0] = pow2[0] = 1;
  17.     for(int i=1; i<n; ++i) {
  18.         pow1[i] = (pow1[i-1] * P1) % MOD1;
  19.         pow2[i] = (pow2[i-1] * P2) % MOD2;
  20.     }
  21. }
  22.  
  23. void init(string s) {
  24.     h1[0] = h2[0] = 0;
  25.     for(int i=0; i<(int) s.size(); ++i) {
  26.         h1[i+1] = (h1[i] * P1 + s[i]) % MOD1;
  27.         h2[i+1] = (h2[i] * P2 + s[i]) % MOD2;
  28.     }
  29. }
  30.  
  31. inline ll hashval(int l, int r) {
  32.     ll a = (h1[r+1] - h1[l] * pow1[r-l+1]) % MOD1;
  33.     if(a < 0) a += MOD1;
  34.     ll b = (h2[r+1] - h2[l] * pow2[r-l+1]) % MOD2;
  35.     if(b < 0) b += MOD2;
  36.     return (a<<32) | b;
  37. }




##########################################################################################

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cout << "Enter Number of Process : ";
    cin >> n;

int processes[n], bt[n], wt[n], tat[n], total_wt = 0, total_tat = 0;

cout << "Enter Processes Time : ";
for(int i=0;i<n;i++)
        cin >> processes[i];

    cout << "Enter Burst Time : ";
    for(int i=0;i<n;i++)
        cin >> bt[i];

wt[0] = 0;
for(int i = 1; i < n ; i++ )
wt[i] = bt[i-1] + wt[i-1];

    for(int i = 0; i < n ; i++)
tat[i] = bt[i] + wt[i];

for(int i=0;i<n;i++)
{
    total_wt += wt[i];
    total_tat += tat[i];
}

cout << "Average waiting time :: " << (double)total_wt / (double)n;

cout << "\nAverage turn around time :: " << (float)total_tat / (float)n;

return 0;
}

#######################################################################################

#include <bits/stdc++.h>

using namespace std;

void first_come_first_server(vector<int> burst){
        int length = burst.size();
        int recent_wait_time = 0;
        int total_wait_time = 0;
        for(int i = 0; i < length; i++){
                cout << recent_wait_time << "  P" << i << "  ";
                recent_wait_time += burst[i];
                total_wait_time += recent_wait_time;
        }
        cout << recent_wait_time << "\n";
        total_wait_time -= recent_wait_time;
        double average_wait_time = (double) total_wait_time / length;
        cout << "Average wait time : " << average_wait_time << "\n";
        burst.clear();
}

bool comp(pair<string, int> a, pair<string, int> b){
        return a.second < b.second;
}

void shortest_job_first(vector<pair<string,int>> job){
        sort(job.begin(), job.end(), comp);
        int length = job.size();
        int recent_wait_time = 0;
        int total_wait_time = 0;
        for(int i = 0; i < length; i++){
                cout << recent_wait_time << "  " << job[i].first << "  ";
                recent_wait_time += job[i].second;
                total_wait_time += recent_wait_time;
        }
        cout << recent_wait_time << "\n";
        total_wait_time -= recent_wait_time;
        double average_wait_time = (double) total_wait_time / length;
        cout << "Average wait time : " << average_wait_time << "\n";
        job.clear();
}

int main(){
        while(true){
                cout << "Enter 1 for firstComeFirstServer Algorithm\nEnter 2 for shortestJobFirst Algorithm\nEnter 0 for exit\n";
                int check = 0;
                cin >> check;
                if(check == 1){
                        cout << "Enter the amount of job : ";
                        int amount;
                        cin >> amount;
                        vector<int> burst;
                        for(int i = 0; i < amount; i++){
                                cout << "Enter burst time of " << i+1 << "# job : ";
                                int temp;
                                cin >> temp;
                                burst.push_back(temp);
                        }
                        first_come_first_server(burst);
                        burst.clear();
                }
                else if(check == 2){
                        cout << "Enter the amount of job : ";
                        int amount;
                        cin >> amount;
                        vector<pair<string, int>> job;
                        for(int i = 0; i < amount; i++){
                                cout << "Enter burst time of " << i+1 << "# job : ";
                                int temp;
                                cin >> temp;
                                string job_name = "P" + to_string(i+1);
                                job.push_back(make_pair(job_name, temp));
                        }
                        shortest_job_first(job);
                        job.clear();
                }
                else if(check == 0){
                        cout << "Thanks\n";
                        break;
                }
        }
        return 0;
}

###########################################################################################

#include<bits/stdc++.h> #define mx 100005 using namespace std; int arr[mx]; int tree[mx*3]; void init(int node,int b,int e) { if(b==e){ tree[node]=arr[b]; return; } int left =node*2; int right = node*2+1; int mid=(b+e)/2; init(left,b,mid); init(right,mid+1,e); tree[node]= tree[left]+tree[right]; } int query(int node,int b,int e,int i, int j) { if(b>j || e<i){ return 0; } if(b>=i && e<=j){ return tree[node]; } int left =node*2; int right = node*2+1; int mid=(b+e)/2; int q1=query(left,b,mid,i,j); int q2=query(right,mid+1,e,i,j); return q1+q2; } void update(int node,int b,int e,int i,int newvalue) { if(i>e || i<b) return; if(b>=i && e<=i){ tree[node]=newvalue; return; } int left =node*2; int right = node*2+1; int mid=(b+e)/2; update(left,b,mid,i,newvalue); update(right,mid+1,e,i,newvalue); tree[node]= tree[left]+tree[right]; } int main() { int t,n,q,v,x,y,z; scanf("%d",&t); for(int i=1;i<=t;i++) { printf("Case %d:\n",i); scanf("%d %d",&n,&q); for(int j=0;j<n;j++){ scanf("%d",&arr[j]); } init(1,0,n-1); for(int k=0;k<q;k++) { scanf("%d",&x); if(x==1) { scanf("%d",&y); printf("%d\n",arr[y]); arr[y]=0; update(1,0,n-1,y,0); } else if(x==2) { scanf("%d %d",&y,&z); arr[y]+=z; update(1,0,n-1,y,arr[y]); //printf("%d\n",ans); } else { scanf("%d %d",&y,&z); int ans=query(1,0,n-1,y,z); printf("%d\n",ans); } } } return 0; }


###########################################################################
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define maxn 1000005
  5. int bit[maxn];
  6.  
  7. int sum(int i)
  8. {
  9. int s=0;
  10. for(;i;i-=i&-i)
  11. s+=bit[i];
  12. return s;
  13. }
  14.  
  15. void update(int i)
  16. {
  17. for(;i<maxn;i+=i&-i)
  18. bit[i]++;
  19. }
  20.  
  21. int solve()
  22. {
  23. int n;cin>>n;
  24. int arr[n];
  25. map<int,int>mp;
  26. for(int i=0;i<n;i++)
  27. {
  28. cin>>arr[i];
  29. mp[arr[i]]=0;
  30. }
  32. int x=0;
  33. for(auto &i:mp)
  34. i.second=++x;
  36. for(int i=0;i<n;i++)
  37. arr[i]=mp[arr[i]];
  39. vector<int>l(n,0),r(n,0);
  40. for(int i=0;i<n;i++)
  41. {
  42. l[i]=i-sum(arr[i]);
  43. update(arr[i]);
  44. }
  46. memset(bit,0,sizeof(bit));
  48. for(int i=n-1;i>=0;i--)
  49. {
  50. r[i]=sum(arr[i]-1);
  51. update(arr[i]);
  52. }
  55. int ans=0;
  56. for(int i=0;i<n;i++)
  57. ans+=l[i]*r[i];
  59. cout<<ans<<"\n";
  60. // for(int i=0;i<n;i++)cout<<l[i]<<" ";cout<<"\n";
  61. // for(int i=0;i<n;i++)cout<<r[i]<<" ";cout<<"\n";
  65. }
  66.  
  67. signed main()
  68. {
  69. cin.tie(0);
  70. cout.tie(0);
  71. ios::sync_with_stdio(0);
  73. int t=1;//cin>>t;
  74. while(t--)
  75. solve();
  77. }


#############################################################################
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define pb push_back
#define pii pair<int,int>
#define xx first
#define yy second

using namespace std;

int n,m,q;

vector<int> graf[300005];

int cnt[300005];
pii kveri[300005];

bool vis[300005];
int cale[300005];
int disc[300005];
int out[300005];
int t;
void dfs(int u){
vis[u] = true;
disc[u] = t;
for(int c:graf[u]){
if(vis[c])continue;
t++;
cale[c] = u;
dfs(c);
}
out[u] = t;
}

bool anc(int x, int y){return disc[x] <= disc[y] && out[y] <= out[x];}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);

cin >> n >> m;
ff(i,1,m){
int u,v;
cin >> u >> v;
graf[u].pb(v);
graf[v].pb(u);
}
dfs(1);
cin >> q;
ff(i,1,q){
cin >> kveri[i].xx >> kveri[i].yy;
cnt[kveri[i].xx]++;
cnt[kveri[i].yy]++;
}
int s = 0;
ff(i,1,n)s += (cnt[i]&1);
if(s){
cout << "NO\n" << s/2;
return 0;
}
cout << "YES\n";
ff(i,1,q){
int a = kveri[i].xx;
int b = kveri[i].yy;
vector<int> r;
while(!anc(a, b)){
r.pb(a);
a = cale[a];
}
r.pb(a);
vector<int> l;
while(b != a){
l.pb(b);
b = cale[b];
}
reverse(l.begin(), l.end());
vector<int> ans;
for(int c:r)ans.pb(c);
for(int c:l)ans.pb(c);
cout << ans.size() << "\n";
for(int c:ans)cout << c << " ";
cout << "\n";
}
return 0;
}



#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define endl "\n"
#define fastIO    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int mod =1e9+7;
ll GCD(ll A, ll B) {return (B == 0) ? A : GCD(B, A % B);}
int LCM(int A, int B) {return A * B / GCD(A, B);}
int power(int a,int n){int res=1;while(n){if(n&1) res=(res*1ll*a)%mod;  n=n>>1;a=(a*1ll*a)%mod;}return res;}
// cout<<fixed<<setprecision(9)<<ans<<"\n";
// priority_queue<int, vector<int>, greater<int> >

void dfs(int i,vector<int> &v,vector<bool> &visited,int &cnt)
{
if(visited[i])
  return;
visited[i]=true;
cnt++;
dfs(v[i],v,visited,cnt);
}



void solve()
{
  int n;
  cin>>n;
  set<int> s;
  vector<int> v(n+1);
  
  for(int i=1;i<=n;i++)
  {
  cin>>v[i];
  s.insert(v[i]);
  }
  
  if(s.size()<n)
  {
  cout<<"YES"<<endl;return;
  }
 
  vector<bool> visited(n+1,false);
  int even=0;
  
  for(int i=1;i<=n;i++)
  {
  if(v[i]==i)
     continue;
  if(!visited[i])
   {
    int cnt=0;
    dfs(i,v,visited,cnt);
    if(cnt%2==0)
       even++;
   }   
  }
  
  if(even%2==0)
    cout<<"YES\n";
  else
    cout<<"NO\n";
  
}

 
int main()
{
  fastIO; 
  int t;
  t=1;
  cin>>t;
  while(t--)
      solve();
  return 0;
}



#####################################################################

#include <bits/stdc++.h>
#define ll long long
using namespace std;

void solve()
{
    ll n,k;
    cin >> n >> k ;
    vector<ll> a(n);
    for(int i=0; i<n; i++)
        cin >> a[i];
    sort(a.begin(),a.end());

    vector<ll> pref(n+1);

    for(int i=0; i<n; i++)
        pref[i+1]=pref[i]+a[i];

    ll ans = (ll)1e18;

    for(int i=0; i<n; i++)
    {
        ll cur=i;
        ll sum=pref[n-i]+a[0]*i;

        if(sum>k)
        {
            ll dif=sum-k;
            cur+=(dif+i)/(i+1);
        }

        ans=min(ans,cur);
    }

    cout << ans ;
}

int main()
{
    int t;
    cin >> t;

    while(t--)
    {
        solve();
        cout << "\n";
    }

    return 0;
}

###################################################################
-2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 60

-2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 40 45

-2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 15 40 40 40

-2147483648 0 0 -2147483648 -2147483648 -2147483648 -2147483648 15 15 15 15

-2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648


##########################################################################

#include<bits/stdc++.h>
#define N 1020110
#define ll long long
#define ld long double
#define ull unsigned long long
#define pi pair<int, int>
#define pii pair<ll, int>
#define piii pair<ll, ll>
#define mi map<int, int>
#define mli map<ll, int>
#define mll map<ll, ll>
#define mod 100000007
#define maximum 100000001
#define minimum -100000001
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define point cout<<showpoint<<fixed<<setprecision(8);
using namespace std;

Comments

Post a Comment