Submission #615558

#TimeUsernameProblemLanguageResultExecution timeMemory
615558LucppSorting (IOI15_sorting)C++17
100 / 100
477 ms21784 KiB
#include "sorting.h" #include <bits/stdc++.h> using namespace std; bool solve(int n, vector<int> a, vector<int> ainv, int m, int X[], int Y[], int P[], int Q[]){ vector<int> p(n), pinv(n); for(int i = 0; i < n; i++) p[i] = pinv[i] = i; for(int i = 0; i < m; i++){ swap(p[pinv[X[i]]], p[pinv[Y[i]]]); swap(pinv[X[i]], pinv[Y[i]]); } int cur = 0; for(int i = 0; i < m; i++){ swap(p[X[i]], p[Y[i]]); swap(pinv[p[X[i]]], pinv[p[Y[i]]]); swap(a[X[i]], a[Y[i]]); swap(ainv[a[X[i]]], ainv[a[Y[i]]]); P[i] = Q[i] = 0; while(cur < n && cur == p[ainv[cur]]) cur++; if(cur < n){ P[i] = ainv[cur]; Q[i] = pinv[cur]; swap(a[P[i]], a[Q[i]]); swap(ainv[a[P[i]]], ainv[a[Q[i]]]); } } for(int i = 0; i < n; i++) if(a[i] != i) return false; return true; } int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) { vector<int> a(n), ainv(n); for(int i = 0; i < n; i++) a[i] = S[i], ainv[S[i]] = i; int lo = 0, hi = M-1; for(int mid=(lo+hi)/2; lo<hi; mid=(lo+hi)/2){ if(solve(n, a, ainv, mid, X, Y, P, Q)) hi = mid; else lo = mid+1; } solve(n, a, ainv, lo, X, Y, P, Q); return lo; }
#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...