Submission #43775

#TimeUsernameProblemLanguageResultExecution timeMemory
43775PowerOfNinjaGoSorting (IOI15_sorting)C++14
100 / 100
611 ms21048 KiB
//Power Of Ninja Go #include <bits/stdc++.h> #ifdef atom #include "grader.cpp" #else #include "sorting.h" #endif using namespace std; typedef long long ll; typedef pair<int, int> ii; #define X first #define Y second #define vi vector<int> #define vii vector< ii > #define pb push_back const int maxn = 2e5+5; int a[3*maxn], b[3*maxn]; int x[3*maxn], y[3*maxn]; int arr[maxn]; int revnow[maxn], realnow[maxn], realend[maxn], revend[maxn]; int n, m; bool works(int k) { //printf("try %d\n", k); for(int i = 0; i< n; i++) { realend[i] = arr[i]; realnow[i] = arr[i]; revnow[arr[i]] = i; revend[arr[i]] = i; } for(int i = 0; i< k; i++) { int p = x[i], q = y[i]; int s = realend[p], t = realend[q]; swap(realend[p], realend[q]); swap(revend[s], revend[t]); } int cur = 0; //for(int i = 0; i< n; i++) printf("%d %d\n", realnow[i], realend[i]); for(int i = 0; i< k; i++) { //printf("move %d\n", i); int p = x[i], q = y[i]; int s = realnow[p], t = realnow[q]; swap(revnow[s], revnow[t]); swap(realnow[p], realnow[q]); //for(int i = 0; i< n; i++) printf("%d %d\n", realnow[i], realend[i]); while(cur< n && realend[cur] == cur) { cur++; continue; } if(cur< n) { int rep = realend[cur]; // swap rep and cur in the original array int s = revnow[rep], t = revnow[cur]; swap(realnow[s], realnow[t]); swap(revnow[rep], revnow[cur]); a[i] = s, b[i] = t; //printf("swap %d %d\n", s, t); //swap rep and cur in the final array s = cur, t = revend[cur]; //printf("swapend %d %d\n", s, t); swap(realend[s], realend[t]); swap(revend[rep], revend[cur]); cur++; } else a[i] = b[i] = 0; while(cur< n && realend[cur] == cur) { cur++; continue; } } return cur == n; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; m = M; for(int i = 0; i< N; i++) arr[i] = S[i]; for(int i = 0; i< M; i++) x[i] = X[i], y[i] = Y[i]; bool alreadySorted = 1; for(int i = 0; i< N; i++) if(arr[i] != i) alreadySorted = 0; if(alreadySorted) { return 0; } int lo = 1, hi = M; while(lo< hi) { int mid = (lo+hi)/2; if(works(mid)) hi = mid; else lo = mid+1; } works(lo); for(int i = 0; i< lo; i++) P[i] = a[i], Q[i] = b[i]; return lo; }

Compilation message (stderr)

sorting.cpp: In function 'bool works(int)':
sorting.cpp:58:17: warning: declaration of 's' shadows a previous local [-Wshadow]
             int s = revnow[rep], t = revnow[cur];
                 ^
sorting.cpp:44:13: note: shadowed declaration is here
         int s = realnow[p], t = realnow[q];
             ^
sorting.cpp:58:34: warning: declaration of 't' shadows a previous local [-Wshadow]
             int s = revnow[rep], t = revnow[cur];
                                  ^
sorting.cpp:44:29: note: shadowed declaration is here
         int s = realnow[p], t = realnow[q];
                             ^
#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...