QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726126 | #5423. Perfect Matching | Code_quantum | AC ✓ | 785ms | 40888kb | C++14 | 1.8kb | 2024-11-08 21:45:57 | 2024-11-08 21:45:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define px first
#define py second
#define pb push_back
const int N = 200005;
int n, res, a[N], d[N], dep[N], barl[N], barr[N];
map<int, int> mpl, mpr;
vector<pii> g[N], ans; vector<int> tmp[N]; bool vis[N];
int dfs(int u, int in){
vis[u] = true; res += d[u]; tmp[u].clear();
for(auto now: g[u]){
int v = now.px, id = now.py;
if(id == in) continue;
if(vis[v] && dep[v] < dep[u]){tmp[u].pb(id); continue;}
else if(vis[v]) continue;
dep[v] = dep[u] + 1;
int gt = dfs(v, id);
if(gt) tmp[u].pb(gt);
}
while((int)tmp[u].size() > 1){
int x = tmp[u].back(); tmp[u].pop_back();
int y = tmp[u].back(); tmp[u].pop_back();
ans.pb({x, y});
}
if((int)tmp[u].size() & 1){
ans.pb({in, tmp[u].back()});
return 0;
}
return in;
}
void work(){
scanf("%d", &n); int cntl = 0, cntr = 0;
mpl.clear(); mpr.clear(); ans.clear();
for(int i = 1; i <= n; i ++){
scanf("%d", &a[i]);
barl[++ cntl] = a[i] + i;
barr[++ cntr] = a[i] - i;
}
sort(barl + 1, barl + cntl + 1);
cntl = unique(barl + 1, barl + cntl + 1) - barl - 1;
sort(barr + 1, barr + cntr + 1);
cntr = unique(barr + 1, barr + cntr + 1) - barr - 1;
for(int i = 1; i <= cntl; i ++) mpl[barl[i]] = i;
for(int i = 1; i <= cntr; i ++) mpr[barr[i]] = i;
for(int i = 1; i <= cntl + cntr; i ++){
g[i].clear(); d[i] = dep[i] = 0; vis[i] = false;
}
for(int i = 1; i <= n; i ++){
int x = mpl[a[i] + i], y = mpr[a[i] - i] + cntl;
g[x].pb({y, i}); g[y].pb({x, i}); d[x] ++; d[y] ++;
}
for(int i = 1; i <= cntl + cntr; i ++) if(! vis[i]){
res = 0; dfs(i, 0); if((res / 2) & 1){puts("No"); return;}
}
puts("Yes");
for(auto now: ans) printf("%d %d\n", now.px, now.py);
}
int main(){
int t; scanf("%d", &t);
while(t --) work(); return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 15488kb
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 2 4 3 1 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 403ms
memory: 31508kb
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 78 77 138 137 201 200 244 242 289 287 309 308 315 314 321 320 337 335 382 380 396 395 450 449 459 458 462 461 480 479 517 515 520 518 526 524 556 554 567 566 619 617 660 659 736 734 763 761 790 788 853 851 903 902 933 932 978 977 987 986 1089 1088 1104 1103 1162 1160 1218 1217 1273 1271 1285 128...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 16812kb
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 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 39 40 34 33 32 31 30 29 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 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 68 67 66 65 64 63 62 61 60 59 38 37 35 36 8 7 6 5 4 3 1 2 74 73 72 71 70 69 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 377ms
memory: 40888kb
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 29352 29351 29350 29349 29348 29347 29346 29345 29344 29343 29342 29341 29340 29339 29338 29337 29336 29335 29334 29333 29332 29331 29330 29329 72010 72009 72008 72007 72006 72005 72004 72003 72002 72001 72000 71999 71998 71997 71996 71995 71994 71993 71992 71991 71990 71989 71988 71987 71986 71...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 785ms
memory: 31048kb
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 28 89504 63463 26518 1121 8564 36817 36811 95315 8931 61541 96991 92548 81132 83637 41302 778 34736 4360 12537 2005 99552 92893 97953 30631 58176 19622 70597 26691 37677 67617 66364 10211 27149 57643 44140 11472 17075 95323 35741 12598 23176 10585 9050 28519 68565 10746 21782 63141 47710 5564 17...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 191ms
memory: 16108kb
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 22 23 33 34 47 48 72 73 107 108 127 128 147 148 155 156 179 180 192 193 210 211 260 261 262 263 309 310 318 319 342 343 404 405 406 407 417 418 443 444 455 456 502 503 583 584 599 600 663 664 699 700 704 705 718 719 720 721 727 728 739 740 770 771 857 858 912 913 951 952 962 96...
result:
ok 1000 Cases (1000 test cases)