# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
958622 | 2024-04-06T08:01:51 Z | 12345678 | Sorting (IOI15_sorting) | C++17 | 234 ms | 24140 KB |
#include "sorting.h" #include <bits/stdc++.h> using namespace std; const int nx=2e5+5; int s[nx], rs[nx], loc[nx], idx[nx], ridx[nx], n; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n=N; int l=0, r=N; while (l<=r) { int md=(l+r)/2, cur=0; for (int i=0; i<N; i++) idx[i]=i, ridx[i]=i, s[i]=S[i], rs[s[i]]=i, P[i]=Q[i]=0; for (int i=md-1; i>=0; i--) swap(ridx[idx[X[i]]], ridx[idx[Y[i]]]), swap(idx[X[i]], idx[Y[i]]); for (int i=0; i<md; i++) { swap(ridx[idx[X[i]]], ridx[idx[Y[i]]]); swap(idx[X[i]], idx[Y[i]]); swap(rs[s[X[i]]], rs[s[Y[i]]]); swap(s[X[i]], s[Y[i]]); while (cur<N&&ridx[cur]==rs[cur]) cur++; if (cur<N) P[i]=ridx[cur], Q[i]=rs[cur], swap(rs[s[P[i]]], rs[s[Q[i]]]), swap(s[P[i]], s[Q[i]]), cur++; } while (cur<N&&ridx[cur]==rs[cur]) cur++; if (l==r) return l; if (cur<N) l=md+1; else r=md; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 0 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
6 | Correct | 1 ms | 2392 KB | Output is correct |
7 | Correct | 1 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 0 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
6 | Correct | 1 ms | 2392 KB | Output is correct |
7 | Correct | 1 ms | 2396 KB | Output is correct |
8 | Correct | 1 ms | 2396 KB | Output is correct |
9 | Correct | 1 ms | 2392 KB | Output is correct |
10 | Correct | 1 ms | 2392 KB | Output is correct |
11 | Correct | 1 ms | 2392 KB | Output is correct |
12 | Correct | 1 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 1 ms | 2392 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
6 | Correct | 0 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 0 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
6 | Correct | 1 ms | 2392 KB | Output is correct |
7 | Correct | 1 ms | 2396 KB | Output is correct |
8 | Correct | 1 ms | 2396 KB | Output is correct |
9 | Correct | 1 ms | 2392 KB | Output is correct |
10 | Correct | 1 ms | 2392 KB | Output is correct |
11 | Correct | 1 ms | 2392 KB | Output is correct |
12 | Correct | 1 ms | 2396 KB | Output is correct |
13 | Correct | 1 ms | 2396 KB | Output is correct |
14 | Correct | 1 ms | 2392 KB | Output is correct |
15 | Correct | 1 ms | 2396 KB | Output is correct |
16 | Correct | 1 ms | 2396 KB | Output is correct |
17 | Correct | 1 ms | 2396 KB | Output is correct |
18 | Correct | 0 ms | 2396 KB | Output is correct |
19 | Correct | 1 ms | 2396 KB | Output is correct |
20 | Correct | 1 ms | 2396 KB | Output is correct |
21 | Correct | 1 ms | 2396 KB | Output is correct |
22 | Correct | 2 ms | 2392 KB | Output is correct |
23 | Correct | 1 ms | 2396 KB | Output is correct |
24 | Correct | 2 ms | 2396 KB | Output is correct |
25 | Correct | 1 ms | 2396 KB | Output is correct |
26 | Correct | 1 ms | 2396 KB | Output is correct |
27 | Correct | 2 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2652 KB | Output is correct |
5 | Correct | 1 ms | 2652 KB | Output is correct |
6 | Correct | 1 ms | 2652 KB | Output is correct |
7 | Correct | 2 ms | 2652 KB | Output is correct |
8 | Correct | 1 ms | 2848 KB | Output is correct |
9 | Correct | 1 ms | 2648 KB | Output is correct |
10 | Correct | 1 ms | 2652 KB | Output is correct |
11 | Correct | 1 ms | 2652 KB | Output is correct |
12 | Correct | 1 ms | 2580 KB | Output is correct |
13 | Correct | 2 ms | 2652 KB | Output is correct |
14 | Correct | 1 ms | 2652 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2652 KB | Output is correct |
5 | Correct | 1 ms | 2652 KB | Output is correct |
6 | Correct | 1 ms | 2652 KB | Output is correct |
7 | Correct | 2 ms | 2652 KB | Output is correct |
8 | Correct | 1 ms | 2848 KB | Output is correct |
9 | Correct | 1 ms | 2648 KB | Output is correct |
10 | Correct | 1 ms | 2652 KB | Output is correct |
11 | Correct | 1 ms | 2652 KB | Output is correct |
12 | Correct | 1 ms | 2580 KB | Output is correct |
13 | Correct | 2 ms | 2652 KB | Output is correct |
14 | Correct | 1 ms | 2652 KB | Output is correct |
15 | Correct | 133 ms | 20116 KB | Output is correct |
16 | Correct | 163 ms | 20644 KB | Output is correct |
17 | Correct | 224 ms | 21724 KB | Output is correct |
18 | Correct | 52 ms | 18632 KB | Output is correct |
19 | Correct | 129 ms | 20688 KB | Output is correct |
20 | Correct | 150 ms | 21552 KB | Output is correct |
21 | Correct | 155 ms | 22612 KB | Output is correct |
22 | Correct | 139 ms | 16872 KB | Output is correct |
23 | Correct | 139 ms | 22428 KB | Output is correct |
24 | Correct | 224 ms | 21936 KB | Output is correct |
25 | Correct | 234 ms | 21684 KB | Output is correct |
26 | Correct | 127 ms | 21908 KB | Output is correct |
27 | Correct | 119 ms | 20788 KB | Output is correct |
28 | Correct | 191 ms | 22064 KB | Output is correct |
29 | Correct | 208 ms | 21528 KB | Output is correct |
30 | Correct | 92 ms | 20380 KB | Output is correct |
31 | Correct | 196 ms | 23372 KB | Output is correct |
32 | Correct | 154 ms | 23124 KB | Output is correct |
33 | Correct | 212 ms | 22128 KB | Output is correct |
34 | Correct | 165 ms | 21968 KB | Output is correct |
35 | Correct | 134 ms | 20564 KB | Output is correct |
36 | Correct | 45 ms | 19832 KB | Output is correct |
37 | Correct | 225 ms | 24140 KB | Output is correct |
38 | Correct | 204 ms | 21884 KB | Output is correct |
39 | Correct | 222 ms | 21796 KB | Output is correct |