Submission #330258

#TimeUsernameProblemLanguageResultExecution timeMemory
330258mihai145Sorting (IOI15_sorting)C++14
100 / 100
410 ms40236 KiB
#include "sorting.h" #include <vector> const int NMAX = 2e5; const int MMAX = 30 * NMAX; int n, s[NMAX + 2], aux[NMAX + 2], inv[NMAX + 2]; int x[MMAX + 2], y[MMAX + 2]; bool vis[NMAX + 2]; std::vector <int> curr; std::vector < std::vector <int> > cycles; void dfs(int node) { vis[node] = 1; curr.push_back(node); if(!vis[aux[node]]) dfs(aux[node]); } bool Sorted(int limit) { for(int i = 0; i < n; i++) aux[i] = s[i], vis[i] = 0; for(int i = 0; i < limit; i++) std::swap(aux[x[i]], aux[y[i]]); cycles.clear(); for(int i = 0; i < n; i++) if(!vis[i]) { curr.clear(); dfs(i); cycles.push_back(curr); } int t = 0; for(auto it : cycles) t += ((int)it.size() - 1); return (t <= limit); } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; for(int i = 0; i < n; i++) { s[i] = S[i]; } for(int i = 0; i < M; i++) { x[i] = X[i]; y[i] = Y[i]; } int st = 0, dr = N, sol = -1; while(st <= dr) { int mid = (st + dr) >> 1; if(Sorted(mid)) { sol = mid; dr = mid - 1; } else { st = mid + 1; } } ///to reconstruct the cycles Sorted(sol); std::vector < std::pair<int,int> > moves; for(auto it : cycles) { for(int i = 0; i < (int)it.size() - 1; i++) { moves.push_back({it[i], it[i + 1]}); } } for(int i = 0; i < n; i++) { inv[s[i]] = i; } for(int i = 0; i < sol; i++) { int preX = s[X[i]]; int preY = s[Y[i]]; inv[preX] = Y[i]; inv[preY] = X[i]; std::swap(s[X[i]], s[Y[i]]); if(!moves.empty()) { P[i] = inv[moves.back().first]; Q[i] = inv[moves.back().second]; moves.pop_back(); } else { P[i] = Q[i] = 0; } } return sol; }
#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...