# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
797242 | 2023-07-29T08:26:51 Z | Ronin13 | Sorting (IOI15_sorting) | C++17 | 140 ms | 21764 KB |
#include "sorting.h" #include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define f first #define s second #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define epb emplace_back using namespace std; int findSwapPairs(int n, int s[], int m, int x[], int y[], int P[], int Q[]) { int l = -1, r = m; while(l + 1 < r){ int mid = (l + r) / 2; int b[n]; for(int i = 0; i < n; i++){ b[i] = s[i]; } for(int i = 0; i < mid; i++){ swap(b[x[i]], b[y[i]]); } int pos[n]; int p[n]; for(int i = 0; i < n; i++){ pos[s[i]] = i; p[b[i]] = i; } int a[n]; for(int i = 0; i < n; i++){ a[i] = s[i];; } int ind = 0; for(int i = 0; i < mid; i++){ swap(pos[a[x[i]]], pos[a[y[i]]]); swap(a[x[i]], a[y[i]]); while(ind < n && b[ind] == ind) ind++; if(ind == n) continue; int x = b[ind]; swap(b[ind], b[p[ind]]); swap(p[x], p[ind]); swap(pos[x], pos[ind]); swap(a[pos[x]], a[pos[ind]]); } bool good = true; for(int i = 0; i < n; i++){ if(a[i] != i) good = false; } good ? r = mid : l = mid; } int b[n]; for(int i = 0; i < n; i++){ b[i] = s[i]; } int p[n]; for(int i = 0; i < r; i++){ swap(b[x[i]], b[y[i]]); } int pos[n]; for(int i = 0; i < n; i++){ pos[s[i]] = i; p[b[i]] = i; } int a[n]; for(int i = 0; i < n; i++){ a[i] = s[i];; } int ind = 0; for(int i = 0; i < r; i++){ swap(pos[a[x[i]]], pos[a[y[i]]]); swap(a[x[i]], a[y[i]]); while(ind < n && b[ind] == ind) ind++; if(ind == n) { P[i] = Q[i] = 0; continue; } int x = b[ind]; swap(b[ind], b[p[ind]]); swap(p[x], p[ind]); P[i] = pos[x], Q[i] = pos[ind]; swap(pos[x], pos[ind]); swap(a[pos[x]], a[pos[ind]]); } bool good = true; for(int i = 0; i < n; i++){ if(a[i] != i) good = false; } return r; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 300 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 | 0 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 296 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 300 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 | 0 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 296 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 | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 300 KB | Output is correct |
3 | Correct | 1 ms | 304 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 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 300 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 | 0 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 296 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 | 0 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 300 KB | Output is correct |
15 | Correct | 1 ms | 304 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 | 1 ms | 212 KB | Output is correct |
20 | Correct | 0 ms | 304 KB | Output is correct |
21 | Correct | 1 ms | 432 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 | 468 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 | 1 ms | 444 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 372 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 1 ms | 468 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 | 440 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 444 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 372 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 1 ms | 468 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 | 440 KB | Output is correct |
15 | Correct | 105 ms | 19268 KB | Output is correct |
16 | Correct | 115 ms | 19628 KB | Output is correct |
17 | Correct | 140 ms | 20792 KB | Output is correct |
18 | Correct | 54 ms | 16204 KB | Output is correct |
19 | Correct | 95 ms | 19128 KB | Output is correct |
20 | Correct | 102 ms | 19768 KB | Output is correct |
21 | Correct | 103 ms | 19776 KB | Output is correct |
22 | Correct | 101 ms | 16156 KB | Output is correct |
23 | Correct | 118 ms | 21628 KB | Output is correct |
24 | Correct | 135 ms | 21344 KB | Output is correct |
25 | Correct | 136 ms | 20904 KB | Output is correct |
26 | Correct | 104 ms | 19772 KB | Output is correct |
27 | Correct | 94 ms | 19036 KB | Output is correct |
28 | Correct | 136 ms | 21104 KB | Output is correct |
29 | Correct | 122 ms | 20452 KB | Output is correct |
30 | Correct | 80 ms | 18552 KB | Output is correct |
31 | Correct | 128 ms | 20900 KB | Output is correct |
32 | Correct | 116 ms | 20864 KB | Output is correct |
33 | Correct | 135 ms | 21176 KB | Output is correct |
34 | Correct | 126 ms | 21256 KB | Output is correct |
35 | Correct | 96 ms | 18920 KB | Output is correct |
36 | Correct | 46 ms | 17332 KB | Output is correct |
37 | Correct | 133 ms | 21764 KB | Output is correct |
38 | Correct | 133 ms | 20944 KB | Output is correct |
39 | Correct | 131 ms | 21068 KB | Output is correct |