# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
117856 | 2019-06-17T09:03:14 Z | zubec | Sorting (IOI15_sorting) | C++14 | 213 ms | 28204 KB |
#include "sorting.h" #include <bits/stdc++.h> using namespace std; const int N = 600100; int n, a[N], pos[N]; pair<int, int> pr[N]; pair<int, int> anss[N]; int b[N]; int f(int m){ for (int i = 0; i < n; i++) b[i] = a[i]; for (int i = 1; i <= m; i++){ swap(b[pr[i].first], b[pr[i].second]); } for (int i = 0; i < n; i++){ pos[b[i]] = i; } int ans = 0; for (int i = 0; i < n; i++){ if (b[i] != i){ anss[ans] = {i, b[i]}; ++ans; int ps = b[i]; swap(b[i], b[pos[i]]); swap(pos[ps], pos[i]); } } if (ans > m) return -1; while(ans < m){ anss[ans] = {0, 0}; ++ans; } return ans; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; for (int i = 0; i < n; i++) a[i] = S[i]; for (int i = 0; i < M; i++){ pr[i+1] = {X[i], Y[i]}; } int l = 0, r = M; while(l < r){ int mid = (l+r)>>1; if (f(mid) != -1) r = mid; else l = mid+1; } f(l); for (int i = 0; i < n; i++) pos[S[i]] = i; for (int i = 0; i < l; i++){ swap(pos[S[X[i]]], pos[S[Y[i]]]); swap(S[X[i]], S[Y[i]]); int a = anss[i].first; int b = anss[i].second; P[i] = pos[a]; Q[i] = pos[b]; swap(S[pos[a]], S[pos[b]]); swap(pos[a], pos[b]); } return l; } /** 5 3 0 4 2 1 5 1 1 4 0 2 3 1 4 0 4 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 2 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 | 2 ms | 384 KB | Output is correct |
12 | Correct | 2 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 2 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 | 2 ms | 384 KB | Output is correct |
12 | Correct | 2 ms | 384 KB | Output is correct |
13 | Correct | 2 ms | 384 KB | Output is correct |
14 | Correct | 2 ms | 384 KB | Output is correct |
15 | Correct | 2 ms | 384 KB | Output is correct |
16 | Correct | 2 ms | 384 KB | Output is correct |
17 | Correct | 2 ms | 384 KB | Output is correct |
18 | Correct | 2 ms | 384 KB | Output is correct |
19 | Correct | 2 ms | 384 KB | Output is correct |
20 | Correct | 2 ms | 384 KB | Output is correct |
21 | Correct | 3 ms | 640 KB | Output is correct |
22 | Correct | 3 ms | 640 KB | Output is correct |
23 | Correct | 3 ms | 640 KB | Output is correct |
24 | Correct | 3 ms | 640 KB | Output is correct |
25 | Correct | 3 ms | 640 KB | Output is correct |
26 | Correct | 3 ms | 640 KB | Output is correct |
27 | Correct | 3 ms | 640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 2 ms | 512 KB | Output is correct |
3 | Correct | 3 ms | 640 KB | Output is correct |
4 | Correct | 2 ms | 512 KB | Output is correct |
5 | Correct | 2 ms | 512 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 3 ms | 512 KB | Output is correct |
8 | Correct | 3 ms | 512 KB | Output is correct |
9 | Correct | 2 ms | 512 KB | Output is correct |
10 | Correct | 2 ms | 512 KB | Output is correct |
11 | Correct | 3 ms | 512 KB | Output is correct |
12 | Correct | 2 ms | 512 KB | Output is correct |
13 | Correct | 2 ms | 512 KB | Output is correct |
14 | Correct | 2 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 2 ms | 512 KB | Output is correct |
3 | Correct | 3 ms | 640 KB | Output is correct |
4 | Correct | 2 ms | 512 KB | Output is correct |
5 | Correct | 2 ms | 512 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 3 ms | 512 KB | Output is correct |
8 | Correct | 3 ms | 512 KB | Output is correct |
9 | Correct | 2 ms | 512 KB | Output is correct |
10 | Correct | 2 ms | 512 KB | Output is correct |
11 | Correct | 3 ms | 512 KB | Output is correct |
12 | Correct | 2 ms | 512 KB | Output is correct |
13 | Correct | 2 ms | 512 KB | Output is correct |
14 | Correct | 2 ms | 512 KB | Output is correct |
15 | Correct | 114 ms | 17224 KB | Output is correct |
16 | Correct | 150 ms | 25496 KB | Output is correct |
17 | Correct | 181 ms | 26872 KB | Output is correct |
18 | Correct | 68 ms | 22136 KB | Output is correct |
19 | Correct | 122 ms | 25464 KB | Output is correct |
20 | Correct | 137 ms | 26328 KB | Output is correct |
21 | Correct | 158 ms | 26168 KB | Output is correct |
22 | Correct | 135 ms | 22392 KB | Output is correct |
23 | Correct | 159 ms | 27964 KB | Output is correct |
24 | Correct | 174 ms | 27484 KB | Output is correct |
25 | Correct | 200 ms | 27000 KB | Output is correct |
26 | Correct | 141 ms | 26104 KB | Output is correct |
27 | Correct | 112 ms | 25336 KB | Output is correct |
28 | Correct | 165 ms | 27256 KB | Output is correct |
29 | Correct | 156 ms | 26620 KB | Output is correct |
30 | Correct | 101 ms | 24688 KB | Output is correct |
31 | Correct | 178 ms | 27188 KB | Output is correct |
32 | Correct | 154 ms | 26872 KB | Output is correct |
33 | Correct | 213 ms | 27360 KB | Output is correct |
34 | Correct | 157 ms | 27428 KB | Output is correct |
35 | Correct | 138 ms | 25060 KB | Output is correct |
36 | Correct | 53 ms | 23704 KB | Output is correct |
37 | Correct | 203 ms | 28204 KB | Output is correct |
38 | Correct | 180 ms | 26976 KB | Output is correct |
39 | Correct | 209 ms | 27260 KB | Output is correct |