Submission #874584

#TimeUsernameProblemLanguageResultExecution timeMemory
874584HuyQuang_re_ZeroSorting (IOI15_sorting)C++14
100 / 100
148 ms39732 KiB
#include <bits/stdc++.h> #define ll long long #define db long double #define II pair <ll,ll> #define III pair <ll,II> #define IV pair <vector <int>,vector <int> > #define TII pair <treap*,treap*> #define fst first #define snd second #define BIT(x,i) ((x>>i)&1) #define pi acos(-1) #define to_radian(x) (x*pi/180.0) #define to_degree(x) (x*180.0/pi) #define Log(x) (31-__builtin_clz((int)x)) #define LogLL(x) (63-__builtin_clzll((ll)x)) #include "sorting.h" #define mxn 600005 using namespace std; int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn]; int root(int u) { return (u==r[u]) ? u : r[u]=root(r[u]); } bool check(int k) { for(i=1;i<=n;i++) tg[i]=p[i],r[i]=i; int comp=n; for(i=1;i<=k;i++) swap(p[x[i]],p[y[i]]); for(i=1;i<=n;i++) if(root(i)!=root(p[i])) { r[root(i)]=root(p[i]); comp--; } for(i=1;i<=n;i++) p[i]=tg[i]; return n-comp<=k; } int findSwapPairs(int _n,int _p[],int _m,int _x[],int _y[],int a[],int b[]) { n=_n; for(i=n;i>=1;i--) p[i]=_p[i-1],p[i]++; m=_m; for(i=m;i>=1;i--) x[i]=_x[i-1],y[i]=_y[i-1],x[i]++,y[i]++; int l=0,r=m; while(l<r) { int mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } ///////////////////////////////////////////////////////////////////////////// for(i=1;i<=n;i++) tg[i]=p[i]; vector <II> vec; for(i=1;i<=l;i++) swap(p[x[i]],p[y[i]]); for(i=1;i<=n;i++) if(visited[i]==0) { int u=i; while(p[u]!=i) { //cerr<<u-1<<" "<<p[u]-1<<'\n'; vec.push_back({ u,p[u] }),u=p[u],visited[u]=1; } visited[u]=1; } for(i=1;i<=n;i++) vec.push_back({ i,i }); reverse(vec.begin(),vec.end()); for(i=1;i<=n;i++) p[i]=tg[i]; ////////////////////////////////////////////////////////////////////////////////// cerr<<'\n'; for(i=1;i<=n;i++) pos[p[i]]=i; int res=0; for(i=1;i<=l;i++) { swap(pos[p[x[i]]],pos[p[y[i]]]); swap(p[x[i]],p[y[i]]); /* cout<<x[i]-1<<" "<<y[i]-1<<'\n'; for(int i=1;i<=n;i++) cout<<p[i]-1<<" "; cout<<'\n'; */ int u=pos[vec.back().fst],v=pos[vec.back().snd]; vec.pop_back(); swap(pos[p[u]],pos[p[v]]); swap(p[u],p[v]); /* cout<<u-1<<" "<<v-1<<'\n'; for(int i=1;i<=n;i++) cout<<p[i]-1<<" "; cout<<'\n';*/ a[res]=u-1; b[res]=v-1; res++; } return res; } /* int main() { freopen("sorting.inp","r",stdin); freopen("sorting.out","w",stdout); cin>>n; for(i=0;i<n;i++) cin>>p[i]; cin>>m; for(i=0;i<m;i++) cin>>x[i]>>y[i]; cout<<(res=findSwapPairs(n,p,m,x,y,a,b))<<'\n'; for(i=0;i<res;i++) cout<<a[i]<<" "<<b[i]<<'\n'; } */

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:35:72: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   35 | int findSwapPairs(int _n,int _p[],int _m,int _x[],int _y[],int a[],int b[])
      |                                                                    ~~~~^~~
sorting.cpp:19:80: note: shadowed declaration is here
   19 | int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
      |                                                                                ^
sorting.cpp:35:64: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   35 | int findSwapPairs(int _n,int _p[],int _m,int _x[],int _y[],int a[],int b[])
      |                                                            ~~~~^~~
sorting.cpp:19:73: note: shadowed declaration is here
   19 | int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
      |                                                                         ^
sorting.cpp:41:13: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   41 |     int l=0,r=m;
      |             ^
sorting.cpp:19:33: note: shadowed declaration is here
   19 | int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
      |                                 ^
sorting.cpp:70:9: warning: declaration of 'res' shadows a global declaration [-Wshadow]
   70 |     int res=0;
      |         ^~~
sorting.cpp:19:69: note: shadowed declaration is here
   19 | int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
      |                                                                     ^~~
#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...