#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
int l = 0,r = M;
while(l < r){
int m = (l + r)/2;
vector<int> v;
vector<int> pos2(N,0);
for(int i = 0;i<N;i++){
v.push_back(S[i]);
pos2[S[i]] = i;
}
vector<int> ord(N,0);
iota(ord.begin(),ord.end(),0);
vector<int> pos = ord;
for(int i = m-1;i>=0;i--){
pos[ord[Y[i]]] = X[i];
pos[ord[X[i]]] = Y[i];
swap(ord[X[i]],ord[Y[i]]);
}
int last = -1;
for(int i = 0;i<m;i++){
pos[ord[Y[i]]] = X[i];
pos[ord[X[i]]] = Y[i];
swap(ord[X[i]],ord[Y[i]]);
pos2[v[Y[i]]] = X[i];
pos2[v[X[i]]] = Y[i];
swap(v[X[i]],v[Y[i]]);
last++;
while(last < N && pos2[last] == pos[last]){
last++;
}
if(last < N){
pos2[v[pos[last]]] = pos2[last];
swap(v[pos2[last]],v[pos[last]]);
pos2[last] = pos[last];
}
}
if(is_sorted(v.begin(),v.end())){
r = m;
}
else l = m + 1;
}
int m = l;
vector<int> v;
vector<int> pos2(N,0);
for(int i = 0;i<N;i++){
v.push_back(S[i]);
pos2[S[i]] = i;
}
vector<int> ord(N,0);
iota(ord.begin(),ord.end(),0);
vector<int> pos = ord;
for(int i = m-1;i>=0;i--){
pos[ord[Y[i]]] = X[i];
pos[ord[X[i]]] = Y[i];
swap(ord[X[i]],ord[Y[i]]);
}
int last = -1;
for(int i = 0;i<m;i++){
pos[ord[Y[i]]] = X[i];
pos[ord[X[i]]] = Y[i];
swap(ord[X[i]],ord[Y[i]]);
pos2[v[Y[i]]] = X[i];
pos2[v[X[i]]] = Y[i];
swap(v[X[i]],v[Y[i]]);
last++;
P[i] = Q[i] = 0;
while(last < N && pos2[last] == pos[last]){
last++;
}
// for(auto u:v){
// cout << u << ' ';
// }
// cout << endl;
// cout << last << endl;
// cout << pos[last] << ' ' << pos2[last] << endl;
if(last < N){
P[i] = pos2[last];
Q[i] = pos[last];
pos2[v[pos[last]]] = pos2[last];
swap(v[pos2[last]],v[pos[last]]);
pos2[last] = pos[last];
}
// for(auto u:v){
// cout << u << ' ';
// }
// cout << endl;
}
assert(is_sorted(v.begin(),v.end()));
return m;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
296 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
296 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
440 KB |
Output is correct |
22 |
Correct |
1 ms |
436 KB |
Output is correct |
23 |
Correct |
1 ms |
444 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
1 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
436 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
436 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
444 KB |
Output is correct |
14 |
Correct |
1 ms |
440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
436 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
436 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
444 KB |
Output is correct |
14 |
Correct |
1 ms |
440 KB |
Output is correct |
15 |
Correct |
131 ms |
17296 KB |
Output is correct |
16 |
Correct |
153 ms |
17676 KB |
Output is correct |
17 |
Correct |
178 ms |
18496 KB |
Output is correct |
18 |
Correct |
75 ms |
16708 KB |
Output is correct |
19 |
Correct |
133 ms |
18220 KB |
Output is correct |
20 |
Correct |
141 ms |
18808 KB |
Output is correct |
21 |
Correct |
135 ms |
18836 KB |
Output is correct |
22 |
Correct |
117 ms |
13860 KB |
Output is correct |
23 |
Correct |
167 ms |
19272 KB |
Output is correct |
24 |
Correct |
193 ms |
19096 KB |
Output is correct |
25 |
Correct |
196 ms |
18724 KB |
Output is correct |
26 |
Correct |
140 ms |
18828 KB |
Output is correct |
27 |
Correct |
136 ms |
18344 KB |
Output is correct |
28 |
Correct |
181 ms |
18952 KB |
Output is correct |
29 |
Correct |
170 ms |
18632 KB |
Output is correct |
30 |
Correct |
112 ms |
18192 KB |
Output is correct |
31 |
Correct |
169 ms |
18984 KB |
Output is correct |
32 |
Correct |
139 ms |
18604 KB |
Output is correct |
33 |
Correct |
182 ms |
18960 KB |
Output is correct |
34 |
Correct |
156 ms |
18820 KB |
Output is correct |
35 |
Correct |
134 ms |
17948 KB |
Output is correct |
36 |
Correct |
69 ms |
17752 KB |
Output is correct |
37 |
Correct |
185 ms |
19512 KB |
Output is correct |
38 |
Correct |
181 ms |
18736 KB |
Output is correct |
39 |
Correct |
181 ms |
18888 KB |
Output is correct |