제출 #438394

#제출 시각아이디문제언어결과실행 시간메모리
438394ruadhan정렬하기 (IOI15_sorting)C++11
54 / 100
236 ms16256 KiB
#include "sorting.h" #include <bits/stdc++.h> using namespace std; const int MX = 1e5 + 5; int n, m; vector<int> s, x, y; vector<int> a, revA, en, revEn; bool valid(int t) { a = s; for (int i = 0; i < t; i++) swap(a[x[i]], a[y[i]]); for (int i = 0; i < n; i++) revA[a[i]] = i; int cnt = 0; for (int i = 0; i < n; i++) if (a[i] != i) { int j = revA[i]; swap(revA[a[i]], revA[a[j]]); swap(a[i], a[j]); cnt++; } return cnt <= t; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N, m = M; s.resize(N), x.resize(N), y.resize(N), a.resize(N), revA.resize(N), en.resize(N), revEn.resize(N); for (int i = 0; i < N; i++) { s.at(i) = S[i]; x.at(i) = X[i]; y.at(i) = Y[i]; } int R = 0; int l = 0, r = M; while (l != r) { int mid = (l + r) / 2; if (!valid(mid)) l = mid + 1; else r = mid; } R = l; a = s; for (int i = 0; i < n; i++) revA[a[i]] = i; en = a; for (int i = 0; i < R; i++) swap(en[x[i]], en[y[i]]); for (int i = 0; i < n; i++) revEn[en[i]] = i; queue<pair<int, int>> changes; vector<int> tmp = en; for (int i = 0; i < n; i++) if (tmp[i] != i) { int j = revEn[i]; swap(revEn[tmp[i]], revEn[tmp[j]]); swap(tmp[i], tmp[j]); changes.push({i, j}); } for (int i = 0; i < R; i++) { swap(revA[a[x[i]]], revA[a[y[i]]]); swap(a[x[i]], a[y[i]]); if (!changes.empty()) { auto change = changes.front(); changes.pop(); P[i] = revA[en[change.first]]; Q[i] = revA[en[change.second]]; swap(en[change.first], en[change.second]); swap(revA[a[P[i]]], revA[a[Q[i]]]); swap(a[P[i]], a[Q[i]]); } else P[i] = Q[i] = 1; } 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...