Submission #71566

#TimeUsernameProblemLanguageResultExecution timeMemory
71566Sa1378Sorting (IOI15_sorting)C++17
20 / 100
4 ms512 KiB
#include "sorting.h" #include <bits/stdc++.h> using namespace std; #define N ((int)201*1000) int b[N],pos[N]; bool mark[N]; int findSwapPairs(int n, int a[], int m, int x[], int y[], int p[], int q[]) { bool flg=1; for(int i=0;i<n;i++)if(a[i]!=i)flg=0; if(flg)return 0; int l=0,r=m+1; vector <pair<int,int> > res; while(l<r-1) { int mid=(l+r)/2; for(int i=0;i<n;i++)b[i]=a[i],mark[i]=0; for(int i=0;i<mid;i++)swap(b[x[i]],b[y[i]]); vector <pair<int,int> > vec; for(int i=0;i<n;i++) if(!mark[i]) { mark[i]=1; if(b[i]==i)continue; int j=b[i];vec.push_back({i,j}); while(!mark[j]) { mark[j]=1; if(!mark[b[j]])vec.push_back({j,b[j]}); j=b[j]; } } if(vec.size()>mid)l=mid; else r=mid,res.swap(vec); } for(int i=0;i<n;i++)pos[a[i]]=i; for(int i=0;i<r;i++) { swap(pos[a[x[i]]],pos[a[y[i]]]); swap(a[x[i]],a[y[i]]); p[i]=pos[res[i].first];q[i]=pos[res[i].second]; swap(pos[res[i].first],pos[res[i].second]); swap(a[pos[res[i].first]],a[pos[res[i].second]]); } return r; }

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:35:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(vec.size()>mid)l=mid;
      ~~~~~~~~~~^~~~
#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...