Submission #1191199

#TimeUsernameProblemLanguageResultExecution timeMemory
1191199AgageldiSorting (IOI15_sorting)C++20
0 / 100
28 ms532 KiB
#include "bits/stdc++.h" // #include "grader.cpp" #include "sorting.h" using namespace std; #define ff first #define ss second int a[300000], vis[300000], b[300000], vip[300000]; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { for(int i = 0; i < N; i++) { a[i] = S[i]; } sort(a, a + N); int f = 1; for(int i = 0; i < N; i++) { if(a[i] != S[i]) f = -1; a[i] = S[i]; } if(~f) return 0; for(int i = 0; i < M; i++) { swap(a[X[i]], a[Y[i]]); for(int j = 0; j < N; j++) { b[j] = a[j]; vip[a[j]] = j; } deque <pair <int,int>> v, ans; for(int j = 0; j < N; j++) { if(b[j] == j) continue; v.push_back({b[j], b[vip[j]]}); swap(b[j], b[vip[j]]); swap(vip[j],vip[b[j]]); } if((int)v.size() > i + 1) continue; for(int j = 0; j < N; j++) { a[j] = S[j]; vis[a[j]] = j; } for(int j = 0; j <= i; j++) { ans.push_back({X[j],Y[j]}); swap(vis[a[X[j]]],vis[a[Y[j]]]); if((int)v.size()) { ans.push_back({vis[v[0].ff], vis[v[0].ss]}); swap(vis[v[0].ff], vis[v[0].ss]); v.pop_front(); } else { ans.push_back({0,0}); } } for(int j = 0; j < N; j++) { P[j] = ans[j].ff; Q[j] = ans[j].ss; } return (i + 1) * 2; } return 1; }
#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...