Submission #71489

#TimeUsernameProblemLanguageResultExecution timeMemory
71489RezwanArefin01Sorting (IOI15_sorting)C++17
100 / 100
282 ms13176 KiB
#include <bits/stdc++.h> #include "sorting.h" using namespace std; const int N = 2e5 + 10; int p[N], pos[N]; int tp[N], tq[N]; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { bool flag = 1; for(int i = 0; i < N - 1; i++) flag &= S[i] < S[i + 1]; if(flag) return 0; auto check = [&](int t) { for(int i = 0; i < N; i++) p[i] = S[i]; for(int i = 0; i <= t; i++) swap(p[X[i]], p[Y[i]]); for(int i = 0; i < N; i++) pos[p[i]] = i; int cnt = 0; for(int i = 0; i < N; i++) { if(p[i] != i) { tp[cnt] = i; tq[cnt++] = p[i]; int x = p[i]; swap(p[i], p[pos[i]]); pos[x] = pos[i]; } } return cnt; }; int lo = 0, hi = M, ans = -1; while(lo <= hi) { int mid = lo + hi >> 1; if(check(mid) <= mid + 1) ans = mid, hi = mid - 1; else lo = mid + 1; } for(int i = check(ans); i <= ans; i++) tp[i] = tq[i] = 0; for(int i = 0; i < N; i++) p[i] = S[i]; for(int i = 0; i < N; i++) pos[p[i]] = i; auto fn = [&](int i, int j) { pos[p[i]] = j; pos[p[j]] = i; swap(p[i], p[j]); }; for(int i = 0; i <= ans; i++) { fn(X[i], Y[i]); P[i] = pos[tp[i]]; Q[i] = pos[tq[i]]; fn(P[i], Q[i]); } return 1 + ans; }

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:9:76: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                                                            ^
sorting.cpp:5:11: note: shadowed declaration is here
 const int N = 2e5 + 10; 
           ^
sorting.cpp:32:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lo + hi >> 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...