제출 #1198998

#제출 시각아이디문제언어결과실행 시간메모리
1198998n3rm1n정렬하기 (IOI15_sorting)C++20
20 / 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[s[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(pos[i], i)); // cout << "swap " << i << " " << pos[i] << endl; 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 = 0; i < res; ++ i) { swap(val[sx[i]], val[sy[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[curr.first], val[curr.second]); } 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...