Submission #401126

#TimeUsernameProblemLanguageResultExecution timeMemory
401126kshitij_sodaniSorting (IOI15_sorting)C++14
74 / 100
1086 ms13188 KiB
//#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long llo; #define mp make_pair #define pb push_back #define a first #define b second //#define endl '\n' #include "sorting.h" //int cur[200001]; int it[200001]; int n; int xx[3*200001]; int yy[3*200001]; int pp[3*200001]; int qq[3*200001]; int cur[200001];//position in which it has to end up int cur2[200001];//position in which number is currently ends in //int cur3[2000001];//position which indes up in int cur4[200001]; //int ind5[200001]; //int cur3[200001]; bool check(int mid){ for(int i=0;i<n;i++){ cur[i]=it[i]; } /* for(int i=0;i<n;i++){ cout<<cur[i]<<"<"; } cout<<endl;*/ //cout<<mid<<",,"<<endl; for(int ii=0;ii<n;ii++){ cur4[ii]=ii; //ind5[ii]=i; } for(int j=0;j<mid;j++){ swap(cur4[xx[j]],cur4[yy[j]]); } queue<int> ss; for(int i=0;i<n;i++){ ss.push(i); } for(int j=0;j<n;j++){ cur2[cur4[j]]=j; } for(int i=0;i<mid;i++){ swap(cur[xx[i]],cur[yy[i]]); /*for(int ii=0;ii<n;ii++){ cout<<cur[ii]<<"/"; }*/ //cout<<endl; //cout<<xx[i]<<"<<"<<yy[i]<<endl; /*for(int j=0;j<n;j++){ cout<<cur[j]<<","; } cout<<endl; */ /*for(int ii=0;ii<n;ii++){ cur4[ii]=ii; } for(int j=i+1;j<mid;j++){ swap(cur4[xx[j]],cur4[yy[j]]); }*/ pair<int,int> cur3; cur3.a=cur2[xx[i]]; cur3.b=cur2[yy[i]]; /*for(int j=0;j<n;j++){ if(cur4[j]==xx[i]){ cur3.a=j; } if(cur4[j]==yy[i]){ cur3.b=j; } }*/ swap(cur4[cur3.a],cur4[cur3.b]); swap(cur2[xx[i]],cur2[yy[i]]); /*for(int j=0;j<n;j++){ cur2[cur4[j]]=j; }*/ /*for(int j=0;j<n;j++){ cout<<cur2[j]<<":"; } cout<<endl;*/ int ind=-1; /*while(ss.size()){ int no=ss.front(); ss.pop(); if(cur2[j]!=cur[j]){ ind=j; break; } }*/ for(int j=0;j<n;j++){ if(cur2[j]!=cur[j]){ ind=j; break; } } //cout<<ind<<":"<<endl; if(ind==-1){ pp[i]=0; qq[i]=0; } else{ int ind2=-1; for(int j=0;j<n;j++){ if(cur2[j]==cur[ind]){ ind2=j; break; } } //cout<<ind<<",,,"<<ind2<<endl; swap(cur[ind2],cur[ind]); pp[i]=ind; qq[i]=ind2; } /*for(int j=0;j<n;j++){ cout<<cur[j]<<","; } cout<<endl; */ /*for(int j=0;j<mid;j++){ }*/ } for(int i=0;i<n;i++){ if(cur[i]!=i){ return false; } } /* for(int i=0;i<n;i++){ cout<<cur[i]<<"<"; } cout<<endl;*/ return true; } int findSwapPairs(int nn, int aa[], int m, int x[], int y[], int p[], int q[]){ n=nn; for(int i=0;i<n;i++){ it[i]=aa[i]; //cout<<it[i]<<","; } //cout<<endl; for(int i=0;i<m;i++){ xx[i]=x[i]; yy[i]=y[i]; } int low=-1; for(int j=19;j>=0;j--){ if(low+(1<<j)<=m){ if(check(low+(1<<j))==false){ low+=(1<<j); } } } low+=1; //cout<<low<<":"<<endl; check(low); for(int i=0;i<low;i++){ p[i]=pp[i]; q[i]=qq[i]; } return low; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...