#include "sorting.h"
#include <cstdio>
#include <algorithm>
using namespace std;
int tree[200006], tree_cnt[524288];
int query(int i, int b, int e) {
if (b == e) return b;
int m = (b + e) / 2;
if (tree_cnt[i * 2 + 1] < m - b + 1) return query(i * 2 + 1, b, m);
else return query(i * 2 + 2, m + 1, e);
}
int update(int i, int b, int e, int p, int v) {
if (p < b || e < p) return tree_cnt[i];
if (b == e) return tree_cnt[i] = v;
int m = (b + e) / 2;
return tree_cnt[i] = update(i * 2 + 1, b, m, p, v) + update(i * 2 + 2, m + 1, e, p, v);
}
int curr[200006], curr_rev[200006];
bool visited[200006];
int getCycle(int n) {
int cnt = 0;
for (int i = 0; i < n; i++) visited[i] = false;
for (int i = 0; i < n; i++) if (!visited[i]) {
int j = curr[i];
visited[i] = true;
while (j != i) {
visited[j] = true;
j = curr[j];
}
cnt++;
}
return cnt;
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
auto f = [&](int z) {
for (int i = 0; i < n; i++) curr[i] = s[i];
for (int t = 0; t < z; t++) swap(curr[x[t]], curr[y[t]]);
return n - getCycle(n);
};
int l = 0, r = m;
while (l < r) {
int mid = (l + r) / 2;
if (f(mid) <= mid) r = mid;
else l = mid + 1;
}
for (int i = 0; i < n; i++) tree[i] = s[i], curr[i] = curr_rev[i] = i;
for (int i = 0; i < l; i++) swap(tree[x[i]], tree[y[i]]);
for (int i = 0; i < n; i++) tree_cnt[262143 + i] = tree[i] == i;
for (int i = 262142; i >= 0; i--) tree_cnt[i] = tree_cnt[i * 2 + 1] + tree_cnt[i * 2 + 2];
for (int t = l - 1; t >= 0; t--) {
int it = query(0, 0, 262143);
if (it == n) break;
p[t] = curr_rev[tree[it]];
q[t] = it;
update(0, 0, 262143, it, 1);
swap(curr[p[t]], curr[q[t]]);
swap(curr_rev[curr[p[t]]], curr_rev[curr[q[t]]]);
if (curr[p[t]] == tree[p[t]]) update(0, 0, 262143, p[t], 1);
swap(curr[x[t]], curr[y[t]]);
swap(curr_rev[curr[x[t]]], curr_rev[curr[y[t]]]);
swap(tree[x[t]], tree[y[t]]);
int tmp = tree_cnt[262143 + x[t]];
update(0, 0, 262143, x[t], tree_cnt[262143 + y[t]]);
update(0, 0, 262143, y[t], tmp);
}
return l;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1388 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1388 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1388 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 15 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 19 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 20 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 21 |
Correct |
3 ms |
1644 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1644 KB |
Output is correct |
| 23 |
Correct |
3 ms |
1644 KB |
Output is correct |
| 24 |
Correct |
3 ms |
1644 KB |
Output is correct |
| 25 |
Correct |
2 ms |
1644 KB |
Output is correct |
| 26 |
Correct |
2 ms |
1644 KB |
Output is correct |
| 27 |
Correct |
3 ms |
1644 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
1516 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1516 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1516 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1516 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1516 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1528 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1516 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1516 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1536 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1516 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1528 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1516 KB |
Output is correct |
| 13 |
Correct |
5 ms |
1516 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1516 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
1516 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1516 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1516 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1516 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1516 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1528 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1516 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1516 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1536 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1516 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1528 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1516 KB |
Output is correct |
| 13 |
Correct |
5 ms |
1516 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1516 KB |
Output is correct |
| 15 |
Correct |
328 ms |
20460 KB |
Output is correct |
| 16 |
Correct |
351 ms |
21024 KB |
Output is correct |
| 17 |
Correct |
414 ms |
21996 KB |
Output is correct |
| 18 |
Correct |
72 ms |
17644 KB |
Output is correct |
| 19 |
Correct |
252 ms |
20460 KB |
Output is correct |
| 20 |
Correct |
287 ms |
21100 KB |
Output is correct |
| 21 |
Correct |
281 ms |
21228 KB |
Output is correct |
| 22 |
Correct |
303 ms |
17516 KB |
Output is correct |
| 23 |
Correct |
355 ms |
22928 KB |
Output is correct |
| 24 |
Correct |
400 ms |
22508 KB |
Output is correct |
| 25 |
Correct |
445 ms |
22164 KB |
Output is correct |
| 26 |
Correct |
267 ms |
21100 KB |
Output is correct |
| 27 |
Correct |
245 ms |
20460 KB |
Output is correct |
| 28 |
Correct |
406 ms |
22508 KB |
Output is correct |
| 29 |
Correct |
383 ms |
21740 KB |
Output is correct |
| 30 |
Correct |
178 ms |
19692 KB |
Output is correct |
| 31 |
Correct |
394 ms |
22252 KB |
Output is correct |
| 32 |
Correct |
353 ms |
22204 KB |
Output is correct |
| 33 |
Correct |
426 ms |
22508 KB |
Output is correct |
| 34 |
Correct |
385 ms |
22496 KB |
Output is correct |
| 35 |
Correct |
264 ms |
20332 KB |
Output is correct |
| 36 |
Correct |
54 ms |
18668 KB |
Output is correct |
| 37 |
Correct |
430 ms |
23140 KB |
Output is correct |
| 38 |
Correct |
464 ms |
22380 KB |
Output is correct |
| 39 |
Correct |
432 ms |
22380 KB |
Output is correct |
