Submission #923775

#TimeUsernameProblemLanguageResultExecution timeMemory
923775winter0101Sorting (IOI15_sorting)C++14
0 / 100
1 ms604 KiB
#include<bits/stdc++.h> #include "sorting.h" using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { for1(i,0,M-1)P[i]=Q[i]=0; auto ck=[&](const vector<int>&p){ for1(i,0,N-1)if (p[i]!=i)return false; return true; }; vector<int>tmp(N); for1(i,0,N-1)tmp[i]=S[i]; if (ck(tmp))return 0; vector<pii>step; auto check=[&](int mid){ vector<int>p(N); step.clear(); for1(i,0,N-1)p[i]=S[i]; for1(i,0,mid){ swap(p[X[i]],p[Y[i]]); } vector<bool>vis(N); int ans=0; for1(i,0,N-1){ if (vis[i])continue; auto u=i; int cc=0; while (true){ if (vis[u])break; vis[u]=1; cc++; u=p[u]; } ans+=cc-1; } for1(i,0,N-1){ if (i!=p[i]){ step.pb({p[i],p[p[i]]}); swap(p[i],p[p[i]]); } } if (ans<=mid+1)return true; return false; }; int l=0,r=M-1,ans=M-1; while (l<=r){ int mid=(l+r)/2; if (check(mid)){ ans=mid; r=mid-1; } else l=mid+1; } check(ans); while (sz(step)<ans+1){ step.pb({0,0}); } vector<int>pos(N),s(N); for1(i,0,N-1)pos[S[i]]=i,s[i]=S[i]; for1(i,0,ans){ swap(pos[s[X[i]]],pos[s[Y[i]]]); swap(s[X[i]],s[Y[i]]); P[i]=pos[step[i].fi],Q[i]=pos[step[i].se]; swap(pos[step[i].fi],pos[step[i].se]); swap(s[P[i]],s[Q[i]]); } return ans+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...