QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662744 | #5423. Perfect Matching | ocharin | AC ✓ | 351ms | 24480kb | C++20 | 1.6kb | 2024-10-21 09:47:44 | 2024-10-21 09:47:47 |
Judging History
answer
/*
_/ _/
_/_/ _/_/_/ _/_/_/ _/_/_/ _/ _/_/ _/_/_/
_/ _/ _/ _/ _/ _/ _/ _/_/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/
_/_/ _/_/_/ _/ _/ _/_/_/ _/ _/ _/ _/
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;++i) cin>>a[i];
unordered_map<int,int>mp1,mp2;
int c1=0,c2=n;
vector<vector<array<int,2>>>e(2*n);
for(int i=0;i<n;++i){
int u=i-a[i],v=i+a[i];
if(!mp1.count(u)) mp1[u]=c1++;
if(!mp2.count(v)) mp2[v]=c2++;
u=mp1[u],v=mp2[v];
e[u].push_back({v,i+1});
e[v].push_back({u,i+1});
}
vector<array<int,2>>res;
vector<int>dep(2*n),vis(2*n);
auto dfs=[&](auto dfs,int u)->int{
vis[u]=1;
int cur=0;
for(auto [v,w]:e[u]){
if(vis[v]){
if(dep[v]<=dep[u]) continue;
if(!cur){
cur=w;
}
else{
res.push_back({cur,w});
cur=0;
}
}
else{
dep[v]=dep[u]+1;
int x=dfs(dfs,v);
if(x){
res.push_back({x,w});
}
else{
if(cur){
res.push_back({w,cur});
cur=0;
}
else cur=w;
}
}
}
return cur;
};
for(int i=0;i<2*n;++i){
if(!vis[i]) dfs(dfs,i);
}
if(res.size()*2==n){
cout<<"Yes\n";
for(auto [x,y]:res) cout<<x<<" "<<y<<"\n";
}
else cout<<"No\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T;cin>>T;
while(T--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 4 1 5 2 6 3 Yes 3 1 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 237ms
memory: 21408kb
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 139 79 244 202 310 289 322 316 382 337 451 397 463 460 517 481 526 520 568 556 661 619 763 736 853 790 934 904 988 979 1105 1090 1219 1162 1285 1273 1405 1294 1456 1411 1531 1459 1561 1555 1615 1588 1630 1618 1669 1651 1723 1684 1915 1738 2026 1972 2092 2029 2197 2155 2305 2290 2353 2350 2431 24...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3904kb
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 2 1 4 3 6 5 8 7 11 10 13 12 15 14 17 16 19 18 21 20 23 22 25 24 27 26 28 9 31 30 33 32 34 29 36 35 38 37 40 39 42 41 44 43 46 45 48 47 50 49 52 51 54 53 56 55 58 57 61 60 63 62 65 64 67 66 68 59 71 70 73 72 74 69 77 76 79 78 81 80 83 82 85 84 87 86 89 88 91 90 93 92 95 94 97 96 99 98 100 75 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 215ms
memory: 24480kb
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 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25 28 27 30 29 32 31 34 33 36 35 38 37 40 39 42 41 44 43 46 45 48 47 50 49 52 51 54 53 56 55 58 57 60 59 62 61 64 63 66 65 68 67 70 69 72 71 74 73 76 75 78 77 80 79 82 81 84 83 86 85 88 87 90 89 92 91 94 93 96 95 98 97 100 99 102 ...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 351ms
memory: 24324kb
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 26518 8564 63463 1121 36817 129 95315 8931 96991 61541 1725 1600 81303 70110 16772 13611 34736 778 74032 11544 88310 80993 80608 33052 37233 9560 78597 37367 84943 65442 50244 20961 91157 52881 10333 6609 19162 3408 87006 59542 97729 416 79681 23980 66364 27149 67617 10211 44140 17075 5...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 176ms
memory: 3796kb
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 4 1 9 6 17 16 21 18 25 22 31 27 33 32 42 35 51 47 64 62 79 72 86 82 96 90 103 101 109 107 121 111 145 127 155 147 159 157 166 164 174 169 179 176 192 191 201 195 210 204 229 223 237 230 246 244 260 252 269 262 282 276 293 292 295 294 297 296 303 301 306 304 318 309 329 325 338 ...
result:
ok 1000 Cases (1000 test cases)