QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #130693 | #2789. Sorting | Qwerty1232# | 36 | 112ms | 4060kb | C++20 | 2.4kb | 2023-07-24 19:50:49 | 2024-07-04 00:55:26 |
Judging History
answer
#include "sorting.h"
#include <bits/stdc++.h>
int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
if (0 && std::all_of(X, X + M, [&](int a) { return a == 0; }) && std::all_of(Y, Y + M, [&](int a) { return a == 0; })) {
std::vector<std::pair<int, int>> ans;
std::vector<int> used(n);
for (int i = 0; i < n; i++) {
if (!used[i]) {
int u = i;
do {
int t = S[u];
used[u] = true;
if (t != i) {
ans.push_back({i, t});
}
u = t;
assert(ans.size() < M);
} while (u != i);
}
}
for (int i = 0; i < ans.size(); i++) {
P[i] = ans[i].first;
Q[i] = ans[i].second;
}
return ans.size();
}
auto cum = [&](std::vector<std::pair<int, int>> ans) {
int m = ans.size();
std::vector<int> p(S, S + n);
for (int i = 0; i < m; i++) {
std::swap(p[X[i]], p[Y[i]]);
std::swap(p[ans[i].first], p[ans[i].second]);
}
std::vector<bool> used(n);
int cnt = 0;
for (int i = 0; i < n; i++) {
if (!used[i]) {
int u = i;
do {
used[u] = true;
u = p[u];
} while (u != i);
cnt++;
}
}
return cnt;
};
static std::mt19937 rnd;
for (int iter = 0;; iter++) {
int m = std::min(M, 4 * n);
std::vector<std::pair<int, int>> ans(m);
int sc = cum(ans);
// while (sc < n) {
for (int f = 0; f < 1e5; f++) {
int i = rnd() % m;
std::pair<int, int> pr = {rnd() % n, rnd() % n};
std::swap(ans[i], pr);
int sc2 = cum(ans);
if (sc2 >= sc) {
if (sc2 > sc) {
std::cerr << sc2 << "\n";
}
sc = sc2;
} else {
std::swap(ans[i], pr);
}
}
if (sc == n) {
for (int i = 0; i < ans.size(); i++) {
P[i] = ans[i].first;
Q[i] = ans[i].second;
}
return ans.size();
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 8
Accepted
Test #1:
score: 8
Accepted
time: 6ms
memory: 3732kb
input:
1 0 1 0 0
output:
1 0 0
result:
ok correct
Test #2:
score: 0
Accepted
time: 3ms
memory: 3680kb
input:
2 0 1 4 0 0 0 0 0 0 0 0
output:
4 1 1 1 1 0 0 0 0
result:
ok correct
Test #3:
score: 0
Accepted
time: 7ms
memory: 3744kb
input:
2 1 0 4 0 0 0 0 0 0 0 0
output:
4 1 1 1 0 0 0 0 0
result:
ok correct
Test #4:
score: 0
Accepted
time: 6ms
memory: 3796kb
input:
3 1 0 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
9 1 1 2 2 1 1 1 0 2 2 2 2 1 1 0 0 0 0
result:
ok correct
Test #5:
score: 0
Accepted
time: 11ms
memory: 3792kb
input:
4 3 2 0 1 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
16 2 2 2 2 1 1 1 1 3 2 1 2 1 1 1 1 0 0 3 0 3 3 3 3 3 3 3 3 1 1 1 1
result:
ok correct
Test #6:
score: 0
Accepted
time: 12ms
memory: 3852kb
input:
5 1 4 2 3 0 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
20 3 3 1 1 1 1 1 1 3 3 1 4 1 1 2 2 4 4 1 1 4 4 1 1 3 3 0 1 0 0 1 1 0 0 3 3 1 1 2 2
result:
ok correct
Test #7:
score: 0
Accepted
time: 12ms
memory: 3832kb
input:
5 4 2 1 0 3 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
20 3 3 1 1 1 1 1 1 3 3 3 3 1 1 2 2 4 4 3 4 4 4 1 1 1 2 0 0 0 0 1 1 4 0 3 3 1 1 2 2
result:
ok correct
Subtask #2:
score: 12
Accepted
Test #8:
score: 12
Accepted
time: 6ms
memory: 4012kb
input:
1 0 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
4 0 0 0 0 0 0 0 0
result:
ok correct
Test #9:
score: 0
Accepted
time: 8ms
memory: 3728kb
input:
2 0 1 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
8 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0
result:
ok correct
Test #10:
score: 0
Accepted
time: 112ms
memory: 4060kb
input:
98 82 70 31 12 27 51 84 90 66 8 49 52 74 91 46 7 96 67 63 85 34 50 87 83 58 78 26 39 77 48 2 55 94 25 61 56 53 13 32 86 72 20 37 73 9 93 65 28 18 11 71 59 88 35 76 40 24 36 33 3 17 29 38 5 21 15 79 30 62 92 45 80 64 95 43 75 97 23 16 57 22 60 41 69 0 42 14 10 47 68 19 4 1 6 44 81 54 89 2940 0 0 0 0 ...
output:
392 45 45 55 55 68 68 64 64 84 84 0 0 19 19 1 1 30 74 77 77 36 36 59 29 79 79 30 30 66 66 0 41 29 0 70 70 21 21 32 94 62 62 83 69 27 39 58 33 3 12 86 86 48 63 78 78 0 0 8 79 12 12 85 90 18 18 77 77 3 3 51 51 26 26 79 79 91 27 30 30 14 14 51 51 35 35 94 94 94 94 70 70 49 10 37 7 76 76 55 55 27 27 51 ...
result:
ok correct
Test #11:
score: 0
Accepted
time: 110ms
memory: 3864kb
input:
99 8 14 3 0 98 74 18 10 50 93 49 23 80 2 54 79 90 31 66 38 81 36 42 83 39 7 9 71 59 62 67 4 68 5 70 72 34 95 25 27 45 61 97 48 29 15 46 12 87 22 26 63 77 84 11 85 30 24 40 78 41 1 96 69 94 19 6 65 33 13 52 75 88 82 86 20 92 43 89 47 28 73 35 32 53 60 21 16 37 58 44 76 57 56 17 55 91 51 64 2970 0 0 0...
output:
396 92 92 14 14 0 0 72 72 71 71 49 49 14 34 79 79 89 89 41 41 8 8 84 84 21 21 91 91 0 0 8 0 45 59 88 72 78 78 11 11 79 79 58 40 77 77 44 90 62 29 32 32 94 94 78 78 75 75 50 13 55 55 97 42 42 42 22 22 58 89 26 26 53 53 68 68 0 0 68 68 87 87 0 0 22 49 90 16 38 38 45 89 49 25 37 37 84 53 95 95 67 30 78...
result:
ok correct
Test #12:
score: 0
Accepted
time: 109ms
memory: 3872kb
input:
96 12 91 75 59 44 30 52 63 41 13 93 79 82 60 85 78 50 53 57 8 80 67 34 24 87 17 47 33 83 21 81 40 89 49 32 70 26 9 43 7 11 37 94 36 23 28 90 42 35 25 62 56 20 84 55 45 46 22 77 51 0 69 1 31 54 2 3 58 88 76 5 6 65 92 39 66 15 95 10 27 14 86 72 4 68 18 38 19 64 73 71 74 48 29 61 16 2880 0 0 0 0 0 0 0 ...
output:
384 61 61 53 53 28 28 88 88 39 39 1 67 92 92 39 39 72 13 60 60 87 87 11 11 12 60 6 20 40 61 33 33 84 84 34 86 82 82 3 46 0 0 58 58 61 61 65 65 45 45 70 35 36 36 79 26 3 90 53 25 12 12 33 33 1 1 8 8 9 9 18 18 23 23 5 5 37 37 89 89 55 55 15 15 84 25 83 54 23 23 82 82 37 37 76 63 88 88 39 39 12 12 55 5...
result:
ok correct
Subtask #3:
score: 16
Accepted
Test #13:
score: 16
Accepted
time: 8ms
memory: 3732kb
input:
2 0 1 60 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
output:
8 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0
result:
ok correct
Test #14:
score: 0
Accepted
time: 9ms
memory: 3728kb
input:
5 0 4 1 3 2 150 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 ...
output:
20 3 3 1 1 1 1 1 1 3 3 3 3 1 1 2 2 4 4 1 1 4 4 1 1 4 2 0 0 0 0 1 1 0 0 1 4 1 1 2 2
result:
ok correct
Test #15:
score: 0
Accepted
time: 101ms
memory: 3832kb
input:
96 7 15 12 95 11 50 20 42 81 29 58 80 56 71 63 66 44 6 64 39 2 22 73 1 24 27 69 28 45 25 60 61 5 94 14 65 9 86 68 32 79 37 3 57 34 35 10 88 76 78 21 93 19 53 84 52 4 33 38 55 62 67 77 41 31 48 91 49 51 43 90 8 87 54 16 17 70 46 85 0 75 92 74 47 36 89 30 13 59 26 40 18 82 83 72 23 2880 0 1 0 1 0 1 0 ...
output:
384 72 87 53 53 28 28 88 88 39 39 72 72 92 92 39 39 72 13 26 8 87 87 11 11 0 0 6 20 91 91 33 33 84 84 85 85 82 82 37 37 0 0 58 58 61 61 65 65 45 45 32 32 36 36 44 44 3 90 32 50 52 19 33 33 1 1 8 8 9 9 18 18 23 23 5 5 37 37 86 37 55 55 15 15 0 0 10 10 23 23 38 68 37 37 92 92 88 88 39 39 12 12 55 55 9...
result:
ok correct
Test #16:
score: 0
Accepted
time: 109ms
memory: 3868kb
input:
99 28 2 16 95 73 6 30 90 18 46 82 69 59 4 40 49 33 29 66 86 97 56 22 96 38 35 67 15 83 44 36 72 81 41 76 47 34 87 65 9 92 57 0 55 68 5 32 17 61 50 14 19 58 24 98 48 53 60 45 12 39 3 8 74 88 77 13 85 84 42 79 51 94 70 10 25 75 31 62 27 64 1 80 78 21 37 7 63 52 23 71 20 54 26 43 91 89 93 11 2970 0 1 0...
output:
396 28 62 14 14 95 38 72 72 71 71 49 49 68 68 79 79 89 89 41 41 8 8 84 84 71 86 91 91 0 0 83 83 95 3 98 98 78 83 11 11 79 79 29 17 77 77 82 82 93 93 32 32 20 87 78 78 75 75 67 67 55 55 39 39 42 42 57 46 66 18 26 26 53 53 68 68 55 77 68 68 87 87 96 89 5 5 51 19 38 38 88 64 16 57 37 37 68 68 95 95 45 ...
result:
ok correct
Test #17:
score: 0
Accepted
time: 105ms
memory: 3780kb
input:
99 52 0 59 91 38 87 65 75 48 11 64 60 95 71 62 79 49 30 47 56 33 16 94 8 78 36 13 68 9 35 74 77 80 24 15 83 28 66 12 51 92 84 43 40 4 46 63 57 17 85 42 25 81 14 50 31 72 34 70 88 67 53 6 37 44 45 96 69 2 86 76 55 3 82 22 5 93 39 26 41 98 7 27 1 20 29 23 19 54 18 61 90 89 32 97 73 10 58 21 2970 0 1 0...
output:
396 92 92 14 14 0 0 23 86 71 71 49 49 68 68 79 79 89 89 41 41 8 8 59 2 21 21 91 91 0 0 83 83 33 33 98 98 78 78 77 82 79 79 35 83 77 77 98 32 93 93 32 32 66 12 78 78 75 75 7 48 55 55 39 39 42 42 22 22 0 0 53 72 53 53 46 45 55 77 13 79 87 87 0 0 5 5 7 7 38 38 65 65 22 97 37 37 22 58 62 19 67 67 32 32 ...
result:
ok correct
Test #18:
score: 0
Accepted
time: 11ms
memory: 3988kb
input:
4 0 1 3 2 120 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...
output:
16 2 2 2 2 1 1 1 1 3 2 0 0 1 1 1 1 0 0 2 2 3 3 3 3 3 3 3 3 1 1 1 1
result:
ok correct
Subtask #4:
score: 0
Time Limit Exceeded
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #19:
score: 18
Accepted
time: 6ms
memory: 3748kb
input:
1 0 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
4 0 0 0 0 0 0 0 0
result:
ok correct
Test #20:
score: 0
Accepted
time: 8ms
memory: 3788kb
input:
2 0 1 60 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0
output:
8 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0
result:
ok correct
Test #21:
score: -18
Time Limit Exceeded
input:
481 264 22 307 266 238 227 68 26 13 12 384 162 410 306 374 311 442 38 407 310 280 308 333 146 326 381 367 110 190 33 141 468 153 393 157 415 229 75 276 392 349 348 179 445 317 64 78 20 323 257 292 395 129 259 165 398 151 219 14 116 338 188 243 61 150 84 72 340 155 133 459 464 248 433 124 399 177 62 ...
output:
Unauthorized output
result:
Subtask #5:
score: 0
Time Limit Exceeded
Test #28:
score: 0
Time Limit Exceeded
input:
1800 530 1775 466 953 230 1179 944 752 990 1316 275 1029 158 152 1673 1706 172 115 599 1661 131 699 1112 454 551 1059 291 495 28 67 773 480 839 462 1210 757 879 285 439 3 1429 820 26 1023 942 199 356 625 1705 1421 144 1529 716 7 1485 1027 1599 696 517 1353 456 1389 273 1363 1414 1177 718 41 777 1621...
output:
Unauthorized output
result:
Subtask #6:
score: 0
Skipped
Dependency #5:
0%