QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#790274 | #5423. Perfect Matching | vwxyz | AC ✓ | 819ms | 25696kb | C++23 | 3.2kb | 2024-11-28 09:31:14 | 2024-11-28 09:31:15 |
Judging History
answer
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <cassert>
using namespace std;
pair<map<long long, int>, vector<long long>> Compress(const vector<long long>& lst) {
vector<long long> decomp(lst.begin(), lst.end());
sort(decomp.begin(), decomp.end());
decomp.erase(unique(decomp.begin(), decomp.end()), decomp.end());
map<long long, int> comp;
for (int i = 0; i < decomp.size(); ++i) {
comp[decomp[i]] = i;
}
return {comp, decomp};
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int N;
cin >> N;
vector<long long> A(N);
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
const long long INF = 1LL << 60;
vector<long long> to_compress;
for (int i = 0; i < N; ++i) {
to_compress.push_back(A[i] + i);
to_compress.push_back(A[i] - i + INF);
}
auto [comp, decomp] = Compress(to_compress);
int le = comp.size();
vector<vector<pair<int, int>>> graph(le);
for (int n = 0; n < N; ++n) {
int i = comp[A[n] + n];
int j = comp[A[n] - n + INF];
graph[i].emplace_back(j, n);
graph[j].emplace_back(i, n);
}
vector<int> tour;
vector<bool> seen(le, false);
vector<int> parents(le, -1);
for (int x = 0; x < le; ++x) {
if (seen[x]) continue;
queue<int> q;
q.push(x);
seen[x] = true;
while (!q.empty()) {
int current = q.front();
q.pop();
tour.push_back(current);
for (auto& [y, n] : graph[current]) {
if (!seen[y]) {
parents[y] = current;
seen[y] = true;
q.push(y);
}
}
}
}
reverse(tour.begin(), tour.end());
vector<vector<int>> dp(le);
vector<pair<int, int>> ans_lst;
vector<bool> seen_nodes(N, false);
for (int x : tour) {
for (auto& [y, n] : graph[x]) {
if (y == parents[x]) continue;
if (parents[y] == x && !dp[y].empty()) {
ans_lst.emplace_back(n, dp[y].back());
dp[y].pop_back();
} else if (!seen_nodes[n]) {
dp[x].push_back(n);
seen_nodes[n] = true;
}
}
while (dp[x].size() >= 2) {
int a = dp[x].back(); dp[x].pop_back();
int b = dp[x].back(); dp[x].pop_back();
ans_lst.emplace_back(a, b);
}
}
if ((int)ans_lst.size() * 2 == N) {
cout << "Yes\n";
for (auto& [i, j] : ans_lst) {
cout << i + 1 << " " << j + 1 << "\n";
assert(abs(i - j) == abs(A[i] - A[j]));
}
} else {
cout << "No\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3784kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 3 6 2 5 4 1 Yes 3 1 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 435ms
memory: 20212kb
input:
10 100000 0 -1 -2 -3 -4 -5 -2 -7 -8 -9 -10 -9 -12 13 14 15 -16 -17 -18 19 20 19 -22 -21 -20 -25 -26 -27 -28 -27 -26 31 30 29 -34 -35 -34 39 38 37 42 41 42 47 44 45 46 49 48 -53 -52 -51 -56 -55 -54 55 56 57 -58 -59 -60 61 62 63 64 65 64 67 66 69 70 73 72 73 74 73 76 75 74 79 80 81 -84 -83 -84 89 86 8...
output:
Yes 99983 99935 99923 99869 99812 99794 99770 99725 99722 99704 99698 99671 99638 99626 99584 99548 99494 99485 99479 99464 99413 99410 99398 99392 99383 99377 99374 99329 99266 99248 99230 99215 99125 99092 99077 99059 99041 99026 99023 98978 98966 98951 98945 98918 98894 98891 98858 98837 98807 98...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
10 100 28761184 28761185 28761186 28761187 28761188 28761189 28761190 28761191 -20675012 -20675013 -20675014 -20675015 -20675016 -20675017 -20675018 -20675019 -20675020 -20675021 -20675022 -20675023 -20675024 -20675025 -20675026 -20675027 -20675028 -20675029 -20675030 -20675031 -36758138 -36758139 -...
output:
Yes 74 73 72 71 70 69 8 7 6 5 4 3 1 2 38 37 35 36 68 67 66 65 64 63 62 61 60 59 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 34 33 32 31 30 29 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 39 40 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 460ms
memory: 25696kb
input:
10 100000 -40608960 -40608959 -40608958 -40608957 -40608956 -40608955 -40608954 -40608953 -40608952 -40608951 -40608950 -40608949 -40608948 -40608947 -40608946 -40608945 -40608944 -40608943 -40608942 -40608941 -40608940 -40608939 -40608938 -40608937 -40608936 -40608935 -40608934 -40608933 -40608932 ...
output:
Yes 49559 49560 29398 29397 29396 29395 29394 29393 29392 29391 29390 29389 29388 29387 29386 29385 29384 29383 29382 29381 29380 29379 29378 29377 29376 29375 29374 29373 29372 29371 29370 29369 29368 29367 29366 29365 29364 29363 29362 29361 29360 29359 29358 29357 29356 29355 29353 29354 34124 34...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 819ms
memory: 20984kb
input:
10 100000 0 -1 -2 3 2 5 6 7 -2 1 0 9 12 11 -8 13 8 -7 16 17 -10 19 22 21 22 23 4 -15 -18 -17 -6 -31 -14 25 32 -25 26 27 -32 31 38 -31 -32 -19 -30 -35 46 45 -48 -37 48 41 46 -43 -44 53 56 55 50 -27 52 61 62 -33 -18 19 64 45 46 -57 -8 -25 -26 -11 -22 49 -66 -65 -66 29 78 -15 74 83 12 83 14 85 86 -7 -5...
output:
Yes 55183 37843 74887 78391 81303 70110 97255 65286 82489 94299 15153 78548 92669 15078 89506 79567 85036 34586 63078 56160 58066 67820 89848 84747 35744 34651 76008 75518 58415 80843 78656 60176 84286 74114 85980 64483 59770 20885 93142 89017 97731 91507 88950 59746 70989 92244 24826 72626 38593 89...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 328ms
memory: 3872kb
input:
1000 1000 -2 0 3 4 6 7 4 7 6 9 11 9 10 12 16 13 16 17 18 20 19 19 24 22 25 23 28 25 26 27 30 32 31 34 36 37 34 37 37 40 42 43 44 45 43 44 46 45 50 48 51 49 54 55 52 55 54 57 56 61 60 61 64 65 64 67 65 66 67 68 71 73 73 75 76 77 78 75 76 78 82 79 80 81 83 83 87 88 90 89 90 93 92 93 95 94 96 96 100 97...
output:
No No No No No No Yes 1000 995 993 979 978 960 955 934 919 908 907 895 891 890 884 867 864 863 850 839 835 834 831 829 827 825 824 822 820 807 806 800 789 764 753 746 736 709 698 697 690 688 687 683 682 677 671 669 668 661 656 648 626 615 608 606 601 585 579 578 561 557 535 513 510 507 500 499 490 4...
result:
ok 1000 Cases (1000 test cases)