Submission #1090965

#TimeUsernameProblemLanguageResultExecution timeMemory
1090965owoovoSorting (IOI15_sorting)C++17
74 / 100
205 ms15952 KiB
#include "sorting.h" #include<bits/stdc++.h> using namespace std; int tar[1000010],tarp[1000010],n,x[1000010],y[1000010],s[1000010]; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n=N; for(int i=0;i<M;i++){ x[i+1]=X[i]; y[i+1]=Y[i]; } int l=0,r=M; while(l!=r){ int m=(l+r)>>1,ok=1; //cout<<l<<" "<<r<<" "<<m<<"\n"; for(int i=0;i<N;i++){ tar[i]=i; s[i]=S[i]; } for(int i=m;i>0;i--){ swap(tar[x[i]],tar[y[i]]); } for(int i=0;i<N;i++){ tarp[tar[i]]=i; } int ans=0; for(int i=0;i<N;i++){ if(s[i]==tar[i])continue; int ori=i; while(tarp[s[ori]]!=ori){ P[ans]=tarp[s[ori]]; Q[ans]=ori; swap(s[tarp[s[ori]]],s[ori]); ans++; } } if(ans>m){ l=m+1; }else{ r=m; } } int m=l; for(int i=0;i<N;i++){ tar[i]=i; s[i]=S[i]; } for(int i=m;i>0;i--){ swap(tar[x[i]],tar[y[i]]); } for(int i=0;i<N;i++){ tarp[tar[i]]=i; } if(m!=0){ swap(tar[x[1]],tar[y[1]]); swap(s[x[1]],s[y[1]]); tarp[tar[x[1]]]=x[1]; tarp[tar[y[1]]]=y[1]; } int ans=0; for(int i=0;i<N;i++){ //cout<<s[i]<<" "<<tar[i]<<"\n"; if(s[i]==tar[i])continue; int ori=i; while(ori!=tarp[s[ori]]){ //cout<<now<<" "<<ori<<"\n"; P[ans]=tarp[s[ori]]; Q[ans]=ori; swap(s[tarp[s[ori]]],s[ori]); ans++; if(ans>=m)break; if(ori==x[ans+1])ori=y[ans+1]; else if(ori==y[ans+1])ori=x[ans+1]; swap(tar[x[ans+1]],tar[y[ans+1]]); swap(s[x[ans+1]],s[y[ans+1]]); tarp[tar[x[ans+1]]]=x[ans+1]; tarp[tar[y[ans+1]]]=y[ans+1]; } if(ans>=m)break; } for(int i=0;i<N;i++){ if(s[i]!=tar[i]){ cout<<"?\n"; } } for(int i=ans;i<m;i++)Q[i]=0,P[i]=0; return l; }

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:14:18: warning: unused variable 'ok' [-Wunused-variable]
   14 |   int m=(l+r)>>1,ok=1;
      |                  ^~
#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...