#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
int a[maxn], pos[maxn];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int i,x,l,r,mid,cnt;
int ans;
l = -1; r = M-1;
while(l<=r) {
mid = (l+r)/2;
// printf("MID = %d\n",mid);
//Init
for(i=0;i<N;i++) a[i] = S[i];
for(i=0;i<=mid;i++) swap(a[X[i]], a[Y[i]]);
for(i=0;i<N;i++) pos[a[i]] = i;
//Count
cnt = 0;
for(i=0;i<N;i++) {
x = pos[i];
if(i!=x) {
pos[a[i]] = x;
// printf("------ swap %d %d\n",i,x);
swap(a[i], a[x]);
cnt++;
}
}
//Check
if(cnt<=mid+1) {
ans = mid;
r = mid-1;
}
else l = mid+1;
}
//Init
for(i=0;i<N;i++) a[i] = S[i];
for(i=0;i<=ans;i++) swap(a[X[i]], a[Y[i]]);
for(i=0;i<N;i++) pos[a[i]] = i;
//Count
cnt = 0;
for(i=0;i<N;i++) {
x = pos[i];
if(i!=x) {
pos[a[i]] = x;
// printf("------ swap %d %d\n",i,x);
swap(a[i], a[x]);
P[cnt] = i; Q[cnt] = x;
cnt++;
}
}
while(cnt<=ans) P[cnt] = Q[cnt] = 0, cnt++;
return ans+1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
256 KB |
Output is correct |
3 |
Correct |
3 ms |
332 KB |
Output is correct |
4 |
Correct |
3 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
256 KB |
Output is correct |
3 |
Correct |
3 ms |
332 KB |
Output is correct |
4 |
Correct |
3 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Incorrect |
3 ms |
256 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
256 KB |
Output is correct |
3 |
Correct |
3 ms |
332 KB |
Output is correct |
4 |
Correct |
3 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
13 |
Correct |
3 ms |
384 KB |
Output is correct |
14 |
Incorrect |
3 ms |
256 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |