Submission #1198857

#TimeUsernameProblemLanguageResultExecution timeMemory
1198857n3rm1nSorting (IOI15_sorting)C++20
36 / 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; cnt_cycles ++; } } 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 = 1, 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]; int val1 = a[i]; int val2 = a[pos[i]]; int index1 = i; int index2 = pos[i]; a[index1] = val2; pos[val2] = index1; a[index2] = val1; pos[val1] = index2; } for (int i = res-1; i >= 0; -- i) { if(u.size() == 0)break; 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...