# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1040084 | 2024-07-31T15:54:57 Z | Zicrus | Sorting (IOI15_sorting) | C++17 | 1000 ms | 21072 KB |
#include <bits/stdc++.h> #include "sorting.h" using namespace std; typedef long long ll; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P1[], int Q1[]) { vector<ll> h(N); for (int i = 0; i < N; i++) h[i] = S[i]; ll ooo = 0; for (int i = 0; i < N; i++) { if (h[i] != i) ooo++; } if (ooo == 0) return 0; ll res1 =0; ll low = 1, high = M; while (low < high) { ll g = (low + high) / 2; vector<int> P(M), Q(M); ll res = 0; vector<ll> s = h; vector<ll> order = s; for (int j = 0; j < g; j++) { swap(order[X[j]], order[Y[j]]); } for (int i = 0; i < g; i++) { swap(s[X[i]], s[Y[i]]); int firstOut = -1, id = -1; for (int j = 0; j < N; j++) { if (order[j] != j) { firstOut = order[id = j]; break; } } if (firstOut == -1) { P[res] = Q[res] = 0; res++; } else { auto iter = find(order.begin(), order.end(), id); ll v = *iter; ll id1 = find(s.begin(), s.end(), firstOut) - s.begin(); ll id2 = find(s.begin(), s.end(), v) - s.begin(); swap(s[id1], s[id2]); swap(order[iter - order.begin()], order[id]); P[res] = id1; Q[res] = id2; res++; } firstOut = -1; for (int j = 0; j < N; j++) { if (s[j] != j) { firstOut = s[j]; break; } } if (firstOut == -1) break; } ll ooo = 0; for (int i = 0; i < N; i++) { if (s[i] != i) ooo++; } if (ooo == 0) { res1 = res; high = g; for (int i = 0; i < res; i++) { P1[i] = P[i]; Q1[i] = Q[i]; } } else { low = g+1; } } return res1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 436 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 436 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 436 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 1 ms | 344 KB | Output is correct |
16 | Correct | 1 ms | 348 KB | Output is correct |
17 | Correct | 1 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 7 ms | 604 KB | Output is correct |
22 | Correct | 7 ms | 824 KB | Output is correct |
23 | Correct | 7 ms | 604 KB | Output is correct |
24 | Correct | 6 ms | 604 KB | Output is correct |
25 | Correct | 5 ms | 604 KB | Output is correct |
26 | Correct | 6 ms | 704 KB | Output is correct |
27 | Correct | 6 ms | 604 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 636 KB | Output is correct |
2 | Correct | 41 ms | 656 KB | Output is correct |
3 | Correct | 32 ms | 604 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 9 ms | 600 KB | Output is correct |
6 | Correct | 12 ms | 600 KB | Output is correct |
7 | Correct | 22 ms | 520 KB | Output is correct |
8 | Correct | 33 ms | 636 KB | Output is correct |
9 | Correct | 32 ms | 600 KB | Output is correct |
10 | Correct | 34 ms | 656 KB | Output is correct |
11 | Correct | 32 ms | 604 KB | Output is correct |
12 | Correct | 19 ms | 680 KB | Output is correct |
13 | Correct | 35 ms | 664 KB | Output is correct |
14 | Correct | 1 ms | 600 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 636 KB | Output is correct |
2 | Correct | 41 ms | 656 KB | Output is correct |
3 | Correct | 32 ms | 604 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 9 ms | 600 KB | Output is correct |
6 | Correct | 12 ms | 600 KB | Output is correct |
7 | Correct | 22 ms | 520 KB | Output is correct |
8 | Correct | 33 ms | 636 KB | Output is correct |
9 | Correct | 32 ms | 600 KB | Output is correct |
10 | Correct | 34 ms | 656 KB | Output is correct |
11 | Correct | 32 ms | 604 KB | Output is correct |
12 | Correct | 19 ms | 680 KB | Output is correct |
13 | Correct | 35 ms | 664 KB | Output is correct |
14 | Correct | 1 ms | 600 KB | Output is correct |
15 | Execution timed out | 1091 ms | 21072 KB | Time limit exceeded |
16 | Halted | 0 ms | 0 KB | - |