Submission #1198827

#TimeUsernameProblemLanguageResultExecution timeMemory
1198827n3rm1nSorting (IOI15_sorting)C++20
0 / 100
2 ms2888 KiB
#include<bits/stdc++.h> #define pb push_back #include "sorting.h" using namespace std; const int maxn = 1e5 + 10; int n, m; int s[maxn]; int a[maxn]; int sx[maxn], sy[maxn]; vector < int > g[maxn]; int used[maxn]; void dfs(int beg) { used[beg] = 1; for (auto nb: g[beg]) if(!used[nb])dfs(nb); } bool check(int x) { for (int i = 0; i < n; ++ i) { a[i] = s[i]; g[i].clear(); used[i] = 0; } for (int i = 0; i < x; ++ i) swap(a[sx[i]],a[sy[i]]); int cnt_cycles = 0; for (int i = 0; i < n; ++ i) { if(a[i] != i)g[a[i]].pb(i); else used[i] = 1; } for (int i = 0; i < n; ++ i) { if(used[i])continue; cnt_cycles ++; dfs(i); } return (n - cnt_cycles <= x); } int val[maxn], pos[maxn]; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; m = M; int is = 1; for (int i = 0; i < n; ++ i) { s[i] = S[i]; if(i != s[i])is = 0; } if(is)return 0; for (int i = 0; i < m; ++ i) { sx[i] = X[i]; sy[i] = Y[i]; } int l = 0, r = m, mid, res = m; while(l <= r) { mid = (l + r)/2; if(check(mid)) { res = mid; r = mid - 1; } else l = mid + 1; } for (int i = 0; i < n; ++ i) val[i] = i; check(res); // cout << res << endl; for (int i = 0; i < n; ++ i) { // cout << a[i] << " "; pos[a[i]] = i; } // cout << endl; vector < pair < int, int > > u; for (int i = 0; i < n; ++ i) { if(a[i] == i)continue; u.pb(make_pair(i, pos[i])); // cout << "swap " << i << " " << pos[i] << endl; int curr = a[i]; swap(a[i], a[pos[i]]); swap(pos[curr], pos[i]); } for (int i = res-1; i >= 0; -- i) { pair < int, int > curr = u.back(); u.pop_back(); P[i] = val[curr.first]; Q[i] = val[curr.second]; swap(val[sx[i]], val[sy[i]]); } return res; }
#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...