#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 20;
int A[maxN];
int B[maxN];
int pos[maxN];
int *S;
int *X;
int *Y;
int *P;
int *Q;
int N, M;
bool check(int K) {
for (int i = 0; i < N; i++) {
A[i] = S[i];
pos[A[i]] = i;
B[i] = i;
}
for (int i = K - 1; i >= 0; i--) {
swap(B[X[i]], B[Y[i]]);
}
int cnt = 0;
for (int i = 0; i < N; i++) {
if (pos[B[i]] != i) {
int x = i;
int y = pos[B[i]];
swap(A[x], A[y]);
swap(pos[A[x]], pos[A[y]]);
cnt++;
}
}
return cnt <= K;
}
void build(int K) {
for (int i = 0; i < N; i++) {
A[i] = S[i];
pos[A[i]] = i;
B[i] = i;
}
for (int i = K - 1; i >= 0; i--) {
swap(B[X[i]], B[Y[i]]);
}
vector<pair<int, int>> swaps;
for (int i = 0; i < N; i++) {
if (pos[B[i]] != i) {
int x = i;
int y = pos[B[i]];
swaps.emplace_back(A[x], A[y]);
swap(A[x], A[y]);
swap(pos[A[x]], pos[A[y]]);
}
}
swaps.resize(K, make_pair(0, 0));
for (int i = 0; i < N; i++) {
pos[S[i]] = i;
}
for (int i = 0; i < K; i++) {
int x = X[i];
int y = Y[i];
swap(S[x], S[y]);
swap(pos[S[x]], pos[S[y]]);
x = pos[swaps[i].first];
y = pos[swaps[i].second];
swap(S[x], S[y]);
swap(pos[S[x]], pos[S[y]]);
P[i] = x;
Q[i] = y;
}
}
int findSwapPairs(int _N, int _S[], int _M, int _X[], int _Y[], int _P[], int _Q[]) {
N = _N;
S = _S;
M = _M;
X = _X;
Y = _Y;
P = _P;
Q = _Q;
int lt = 0;
int rt = M;
int K = -1;
while (lt <= rt) {
int mt = (lt + rt) / 2;
if (check(mt)) {
K = mt;
rt = mt - 1;
}
else {
lt = mt + 1;
}
}
build(K);
return K;
}
# |
Verdict |
Execution time |
Memory |
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 |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
328 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
308 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
328 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
308 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
304 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
468 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
1 ms |
452 KB |
Output is correct |
26 |
Correct |
1 ms |
560 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
448 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
444 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
448 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
444 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
82 ms |
18644 KB |
Output is correct |
16 |
Correct |
87 ms |
19248 KB |
Output is correct |
17 |
Correct |
102 ms |
20052 KB |
Output is correct |
18 |
Correct |
48 ms |
15536 KB |
Output is correct |
19 |
Correct |
84 ms |
18452 KB |
Output is correct |
20 |
Correct |
94 ms |
19144 KB |
Output is correct |
21 |
Correct |
90 ms |
19096 KB |
Output is correct |
22 |
Correct |
75 ms |
15500 KB |
Output is correct |
23 |
Correct |
94 ms |
20924 KB |
Output is correct |
24 |
Correct |
103 ms |
20592 KB |
Output is correct |
25 |
Correct |
102 ms |
20328 KB |
Output is correct |
26 |
Correct |
94 ms |
19172 KB |
Output is correct |
27 |
Correct |
93 ms |
18460 KB |
Output is correct |
28 |
Correct |
108 ms |
20356 KB |
Output is correct |
29 |
Correct |
100 ms |
19900 KB |
Output is correct |
30 |
Correct |
70 ms |
17800 KB |
Output is correct |
31 |
Correct |
130 ms |
20320 KB |
Output is correct |
32 |
Correct |
88 ms |
20212 KB |
Output is correct |
33 |
Correct |
104 ms |
20556 KB |
Output is correct |
34 |
Correct |
92 ms |
20568 KB |
Output is correct |
35 |
Correct |
97 ms |
18240 KB |
Output is correct |
36 |
Correct |
42 ms |
16588 KB |
Output is correct |
37 |
Correct |
102 ms |
21128 KB |
Output is correct |
38 |
Correct |
100 ms |
20272 KB |
Output is correct |
39 |
Correct |
97 ms |
20480 KB |
Output is correct |