QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#74540 | #5423. Perfect Matching | magicduck | AC ✓ | 1201ms | 39860kb | C++14 | 2.1kb | 2023-02-02 12:45:19 | 2023-02-02 12:45:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T> inline void read(T &F) {
int R = 1; F = 0; char CH = getchar();
for(; !isdigit(CH); CH = getchar()) if(CH == '-') R = -1;
for(; isdigit(CH); CH = getchar()) F = F * 10 + CH - 48;
F *= R;
}
inline void file(string str) {
freopen((str + ".in").c_str(), "r", stdin);
freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 5e5 + 10;
vector<pair<int, int> > edge[N], R; int n, vis[N], flag[N], f[N];
void dfs(int x) {
//cout << x << endl;
vis[x] = 1;
for(auto i : edge[x]) {
if(vis[i.first]) continue;
f[i.first] = i.second; dfs(i.first);
}
}
void calc(int x) {
for(auto i : edge[x])
if(f[i.first] == i.second) calc(i.first);
for(auto &i : edge[x])
if(i.second == f[x]) swap(i, edge[x].back());
int l = 0;
for(auto i : edge[x]) {
if(flag[i.second]) continue;
if(l) R.emplace_back(l, i.second), flag[l] = flag[i.second] = 1, l = 0;
else l = i.second;
}
}
int main() {
//file("");
int T; read(T);
while(T--) {
read(n); R.clear();
for(int i = 1; i <= n * 4; i++) vis[i] = flag[i] = f[i] = 0, edge[i].clear();
map<int, int> A, B; int tot = 0;
for(int i = 1; i <= n; i++) {
int v; read(v);
const int x = v - i, y = v + i;
if(!A[x]) A[x] = ++tot;
if(!B[y]) B[y] = ++tot;
edge[A[x]].emplace_back(B[y], i);
edge[B[y]].emplace_back(A[x], i);
}
int ans = 1;
for(int i = 1; i <= tot && ans; i++)
if(!vis[i]) {
dfs(i), calc(i);
for(auto j : edge[i])
if(!flag[j.second]) ans = 0;
}
if(!ans) {
puts("No"); continue;
}
puts("Yes");
for(auto i : R) cout << i.first << ' ' << i.second << '\n';
}
#ifdef _MagicDuck
fprintf(stderr, "# Time: %.3lf s", (double)clock() / CLOCKS_PER_SEC);
#endif
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 19764kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 4 1 2 5 3 6 Yes 3 1 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 452ms
memory: 29624kb
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 21 22 77 78 137 138 200 201 242 244 287 289 308 309 314 315 320 321 335 337 380 382 395 396 449 450 458 459 461 462 479 480 515 517 518 520 524 526 554 556 566 567 617 619 659 660 734 736 761 763 788 790 851 853 902 903 932 933 977 978 986 987 1088 1089 1103 1104 1160 1162 1217 1218 1271 1273 12...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 2ms
memory: 20856kb
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 1 2 3 4 5 6 7 8 28 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 9 34 30 31 32 33 29 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 68 60 61 62 63 64 65 66 67 59 74 70 71 72 73 69 100 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 75 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 523ms
memory: 39860kb
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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 1201ms
memory: 31508kb
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 89504 28 63463 8564 26518 1121 36811 36817 95315 8931 96991 61541 81303 70110 16772 13611 34736 778 88310 80993 821 11544 74032 940 80608 33052 9050 10585 78597 37367 41232 84943 65442 50244 91157 52881 5417 10333 18933 19162 97729 3408 59542 87006 79681 23980 67617 27149 66364 10211 57643 17075...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 238ms
memory: 20644kb
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 23 22 34 33 48 47 73 72 108 107 128 127 148 147 156 155 180 179 193 192 211 210 261 260 263 262 310 309 319 318 343 342 405 404 407 406 418 417 444 443 456 455 503 502 584 583 600 599 664 663 700 699 705 704 719 718 721 720 728 727 740 739 771 770 858 857 913 912 952 951 963 96...
result:
ok 1000 Cases (1000 test cases)