Submission #71487

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
714872018-08-24 22:52:17RezwanArefin01Sorting (IOI15_sorting)C++17
0 / 100
3 ms512 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[]) {
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;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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:28: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...