Submission #805058

#TimeUsernameProblemLanguageResultExecution timeMemory
805058tomrukSorting (IOI15_sorting)C++17
100 / 100
196 ms19512 KiB
#include "sorting.h" #include <bits/stdc++.h> using namespace std; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){ int l = 0,r = M; while(l < r){ int m = (l + r)/2; vector<int> v; vector<int> pos2(N,0); for(int i = 0;i<N;i++){ v.push_back(S[i]); pos2[S[i]] = i; } vector<int> ord(N,0); iota(ord.begin(),ord.end(),0); vector<int> pos = ord; for(int i = m-1;i>=0;i--){ pos[ord[Y[i]]] = X[i]; pos[ord[X[i]]] = Y[i]; swap(ord[X[i]],ord[Y[i]]); } int last = -1; for(int i = 0;i<m;i++){ pos[ord[Y[i]]] = X[i]; pos[ord[X[i]]] = Y[i]; swap(ord[X[i]],ord[Y[i]]); pos2[v[Y[i]]] = X[i]; pos2[v[X[i]]] = Y[i]; swap(v[X[i]],v[Y[i]]); last++; while(last < N && pos2[last] == pos[last]){ last++; } if(last < N){ pos2[v[pos[last]]] = pos2[last]; swap(v[pos2[last]],v[pos[last]]); pos2[last] = pos[last]; } } if(is_sorted(v.begin(),v.end())){ r = m; } else l = m + 1; } int m = l; vector<int> v; vector<int> pos2(N,0); for(int i = 0;i<N;i++){ v.push_back(S[i]); pos2[S[i]] = i; } vector<int> ord(N,0); iota(ord.begin(),ord.end(),0); vector<int> pos = ord; for(int i = m-1;i>=0;i--){ pos[ord[Y[i]]] = X[i]; pos[ord[X[i]]] = Y[i]; swap(ord[X[i]],ord[Y[i]]); } int last = -1; for(int i = 0;i<m;i++){ pos[ord[Y[i]]] = X[i]; pos[ord[X[i]]] = Y[i]; swap(ord[X[i]],ord[Y[i]]); pos2[v[Y[i]]] = X[i]; pos2[v[X[i]]] = Y[i]; swap(v[X[i]],v[Y[i]]); last++; P[i] = Q[i] = 0; while(last < N && pos2[last] == pos[last]){ last++; } // for(auto u:v){ // cout << u << ' '; // } // cout << endl; // cout << last << endl; // cout << pos[last] << ' ' << pos2[last] << endl; if(last < N){ P[i] = pos2[last]; Q[i] = pos[last]; pos2[v[pos[last]]] = pos2[last]; swap(v[pos2[last]],v[pos[last]]); pos2[last] = pos[last]; } // for(auto u:v){ // cout << u << ' '; // } // cout << endl; } assert(is_sorted(v.begin(),v.end())); return m; }
#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...