Submission #1173883

#TimeUsernameProblemLanguageResultExecution timeMemory
1173883HappyCapybaraSorting (IOI15_sorting)C++20
100 / 100
116 ms20004 KiB
#include "sorting.h" #include<bits/stdc++.h> using namespace std; int solve(vector<int> v){ vector<bool> seen(v.size(), false); int res = 0; for (int i=0; i<v.size(); i++){ if (seen[i]) continue; seen[i] = true; int j = i; while (!seen[v[j]]){ res++; j = v[j]; seen[j] = true; } } return res; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){ vector<int> f(N), g(N); for (int i=0; i<N; i++){ f[i] = i; g[i] = i; } int l = -1, r = M; while (l != r-1){ int m = (l+r)/2; vector<int> gx = g; for (int i=0; i<m; i++) swap(gx[X[i]], gx[Y[i]]); vector<int> v(N); for (int i=0; i<N; i++) v[i] = S[gx[i]]; if (solve(v) <= m) r = m; else l = m; } for (int i=0; i<r; i++){ swap(g[X[i]], g[Y[i]]); swap(f[g[Y[i]]], f[g[X[i]]]); } vector<int> v(N); for (int i=0; i<N; i++) v[i] = S[g[i]]; unordered_set<int> us; for (int i=0; i<N; i++) us.insert(i); for (int i=0; i<r; i++){ swap(f[X[i]], f[Y[i]]); swap(g[f[Y[i]]], g[f[X[i]]]); P[i] = 0; Q[i] = 0; vector<int> del; for (int j : us){ if (v[j] == j) del.push_back(j); if (v[j] != j){ P[i] = g[j]; Q[i] = g[v[j]]; swap(v[j], v[v[j]]); break; } } for (int j : del) us.erase(j); } return r; }
#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...