QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#130694 | #2789. Sorting | Qwerty1232# | 8 | 13ms | 4076kb | C++20 | 2.5kb | 2023-07-24 19:51:21 | 2024-07-04 00:55:27 |
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);
for (int i = 0; i < m; i++) {
ans[i] = {rnd() % n, rnd() % n};
}
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();
}
}
}
詳細信息
Subtask #1:
score: 8
Accepted
Test #1:
score: 8
Accepted
time: 6ms
memory: 3712kb
input:
1 0 1 0 0
output:
1 0 0
result:
ok correct
Test #2:
score: 0
Accepted
time: 7ms
memory: 3760kb
input:
2 0 1 4 0 0 0 0 0 0 0 0
output:
4 1 1 0 1 1 0 1 1
result:
ok correct
Test #3:
score: 0
Accepted
time: 7ms
memory: 3996kb
input:
2 1 0 4 0 0 0 0 0 0 0 0
output:
4 1 1 0 1 0 0 1 1
result:
ok correct
Test #4:
score: 0
Accepted
time: 8ms
memory: 3732kb
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 2 0 2 1 1 1 1 1 2 1 1 2 2 1 0 2 1 0
result:
ok correct
Test #5:
score: 0
Accepted
time: 7ms
memory: 3996kb
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 0 2 2 1 1 0 2 2 2 3 1 0 1 0 2 1 0 1 1 2 1 1 1 1 0 2 1 3 0 3 1 2
result:
ok correct
Test #6:
score: 0
Accepted
time: 13ms
memory: 3716kb
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 2 1 0 4 1 4 0 4 4 4 4 4 0 1 4 0 2 2 2 1 4 4 3 4 0 0 1 3 1 0 4 2 4 3 1 0 3 3 3 2
result:
ok correct
Test #7:
score: 0
Accepted
time: 13ms
memory: 4000kb
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 2 2 0 4 1 4 0 4 4 4 4 4 1 2 4 0 2 2 2 1 4 4 3 4 2 0 1 3 1 4 4 2 4 3 1 0 3 3 2 2
result:
ok correct
Subtask #2:
score: 0
Time Limit Exceeded
Test #8:
score: 12
Accepted
time: 3ms
memory: 4076kb
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: 3996kb
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 0 1 1 0 0 0 0 1 1 1 1 1 0 1
result:
ok correct
Test #10:
score: -12
Time Limit Exceeded
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:
Unauthorized output
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #13:
score: 16
Accepted
time: 8ms
memory: 3704kb
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 0 1 1 0 0 0 0 1 1 1 1 1 0 1
result:
ok correct
Test #14:
score: 0
Accepted
time: 13ms
memory: 4072kb
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 2 2 0 4 1 4 0 4 4 4 4 4 1 2 4 0 2 2 2 1 4 4 3 4 2 0 1 3 1 0 4 2 4 3 1 0 3 3 3 2
result:
ok correct
Test #15:
score: -16
Time Limit Exceeded
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:
Unauthorized output
result:
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
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%