# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
801990 | 2023-08-02T08:56:22 Z | caganyanmaz | Sorting (IOI15_sorting) | C++17 | 146 ms | 21080 KB |
#include "sorting.h" #define pb push_back #include <bits/stdc++.h> using namespace std; constexpr static int MXSIZE = 2e5; int e[MXSIZE]; int n; int component[MXSIZE]; int *s, *x, *y; void dfs(int node, int c) { component[node] = c; if (component[e[node]] == -1) dfs(e[node], c); } void construct(int k) { for (int i = 0; i < n; i++) e[i] = s[i]; for (int i = 0; i < k; i++) swap(e[x[i]], e[y[i]]); } bool is_possible(int k) { construct(k); for (int i = 0; i < n; i++) component[i] = -1; int last = 0; for (int i = 0; i < n; i++) if (component[i] == -1) dfs(i, last++); return (n-last) <= k; } int rs[MXSIZE]; int findSwapPairs(int nn, int ss[], int _m, int xx[], int yy[], int p[], int q[]) { n = nn; s = ss, x = xx, y = yy; int l = -1, r = _m+1; while (r - l > 1) { int m = l+r>>1; if (is_possible(m)) r = m; else l = m; } construct(r); vector<array<int, 2>> swaps; for (int i = 0; i < n; i++) { while (e[i] != i) { swaps.pb({e[i], e[e[i]]}); swap(e[i], e[e[i]]); } } assert(swaps.size() <= r); for (int i = 0; i < n; i++) { rs[s[i]] = i; e[i] = s[i]; } for (int i = 0; i < r; i++) { swap(e[x[i]], e[y[i]]); rs[e[x[i]]] = x[i]; rs[e[y[i]]] = y[i]; if (i < swaps.size()) { p[i] = rs[swaps[i][0]]; q[i] = rs[swaps[i][1]]; swap(e[p[i]], e[q[i]]); rs[e[p[i]]] = p[i]; rs[e[q[i]]] = q[i]; } else { p[i] = 0; q[i] = 0; } } return r; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 304 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 304 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 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 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 312 KB | Output is correct |
3 | Correct | 1 ms | 320 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 316 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 304 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 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 | 1 ms | 312 KB | Output is correct |
15 | Correct | 1 ms | 320 KB | Output is correct |
16 | Correct | 1 ms | 340 KB | Output is correct |
17 | Correct | 1 ms | 316 KB | Output is correct |
18 | Correct | 1 ms | 212 KB | Output is correct |
19 | Correct | 1 ms | 312 KB | Output is correct |
20 | Correct | 1 ms | 212 KB | Output is correct |
21 | Correct | 1 ms | 468 KB | Output is correct |
22 | Correct | 2 ms | 468 KB | Output is correct |
23 | Correct | 2 ms | 472 KB | Output is correct |
24 | Correct | 2 ms | 472 KB | Output is correct |
25 | Correct | 1 ms | 540 KB | Output is correct |
26 | Correct | 1 ms | 468 KB | Output is correct |
27 | Correct | 1 ms | 468 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 468 KB | Output is correct |
2 | Correct | 1 ms | 448 KB | Output is correct |
3 | Correct | 1 ms | 468 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 | 444 KB | Output is correct |
8 | Correct | 1 ms | 512 KB | Output is correct |
9 | Correct | 1 ms | 512 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 | 468 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 468 KB | Output is correct |
2 | Correct | 1 ms | 448 KB | Output is correct |
3 | Correct | 1 ms | 468 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 | 444 KB | Output is correct |
8 | Correct | 1 ms | 512 KB | Output is correct |
9 | Correct | 1 ms | 512 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 | 468 KB | Output is correct |
15 | Correct | 120 ms | 17904 KB | Output is correct |
16 | Correct | 115 ms | 18276 KB | Output is correct |
17 | Correct | 130 ms | 19736 KB | Output is correct |
18 | Correct | 54 ms | 15460 KB | Output is correct |
19 | Correct | 111 ms | 18568 KB | Output is correct |
20 | Correct | 116 ms | 19080 KB | Output is correct |
21 | Correct | 115 ms | 19148 KB | Output is correct |
22 | Correct | 118 ms | 14668 KB | Output is correct |
23 | Correct | 125 ms | 20008 KB | Output is correct |
24 | Correct | 129 ms | 19968 KB | Output is correct |
25 | Correct | 130 ms | 20056 KB | Output is correct |
26 | Correct | 121 ms | 19008 KB | Output is correct |
27 | Correct | 104 ms | 18320 KB | Output is correct |
28 | Correct | 125 ms | 19608 KB | Output is correct |
29 | Correct | 120 ms | 19708 KB | Output is correct |
30 | Correct | 77 ms | 17856 KB | Output is correct |
31 | Correct | 122 ms | 20248 KB | Output is correct |
32 | Correct | 122 ms | 19332 KB | Output is correct |
33 | Correct | 140 ms | 20176 KB | Output is correct |
34 | Correct | 135 ms | 19948 KB | Output is correct |
35 | Correct | 108 ms | 18328 KB | Output is correct |
36 | Correct | 42 ms | 16620 KB | Output is correct |
37 | Correct | 146 ms | 21080 KB | Output is correct |
38 | Correct | 127 ms | 19936 KB | Output is correct |
39 | Correct | 132 ms | 20520 KB | Output is correct |