QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#272350 | #5423. Perfect Matching | ushg8877 | AC ✓ | 777ms | 104748kb | C++14 | 1.5kb | 2023-12-02 16:58:58 | 2023-12-02 16:58:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
const int MAXN=1e6+5;
map<ll,int> M;int tot=0;
int ls[MAXN],rs[MAXN];
vector<pair<int,int> > ve[2*MAXN];// 到达节点,边编号
vector<int> ans[MAXN];
int n;int a[MAXN];bool vis[MAXN];
bool dfs(int u,int fa){// 是否用完
vis[u]=1;
for(auto i:ve[u]){
if(i.first==fa) continue;
if(vis[i.first]) ans[u].push_back(i.second);
}
for(auto i:ve[u]){
if(vis[i.first]) continue;
if(dfs(i.first,u)) ans[i.first].push_back(i.second);
else ans[u].push_back(i.second);
}
return ans[u].size()&1;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
M.clear();tot=0;
for(int i=1;i<=n;i++){
if(!M[a[i]+i])
M[a[i]+i]=++tot;
ls[i]=M[a[i]+i];
}
M.clear();
for(int i=1;i<=n;i++){
if(!M[a[i]-i])
M[a[i]-i]=++tot;
rs[i]=M[a[i]-i];
}
for(int i=1;i<=tot;i++) ve[i].clear();
for(int i=1;i<=n;i++){
ve[ls[i]].push_back(MP(rs[i],i));
ve[rs[i]].push_back(MP(ls[i],i));
}
for(int i=1;i<=tot;i++) ans[i].clear(),vis[i]=0;
for(int i=1;i<=tot;i++)
if(!vis[i]) dfs(i,0);
for(int i=1;i<=tot;i++)
if(ans[i].size()&1){
cout<<"No"<<endl;
return;
}
cout<<"Yes"<<endl;
for(int i=1;i<=tot;i++)
for(int j=0;j<ans[i].size();j+=2)
cout<<ans[i][j]<<" "<<ans[i][j+1]<<endl;
return;
}
int main(){
// freopen("input.in","r",stdin);
// freopen("answer.out","w",stdout);
ios::sync_with_stdio(false);
int _;cin>>_;
while(_--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 10ms
memory: 77144kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 5 2 6 3 Yes 1 3 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 379ms
memory: 93084kb
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 1 4 6 8 9 10 13 17 18 19 26 27 28 35 59 60 61 85 89 92 108 110 111 112 113 114 115 119 125 131 132 133 134 135 136 143 144 145 153 161 181 186 194 199 204 212 217 218 219 220 221 222 223 230 231 232 234 271 296 297 298 305 306 307 326 329 334 338 341 342 343 347 350 359 360 361 363 390 411 415 4...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 4ms
memory: 79360kb
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 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 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 2 3 4 5 6 7 8 1 36 37 38 35 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 39 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 387ms
memory: 104748kb
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 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 ...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 777ms
memory: 94036kb
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 1 1932 1986 3820 8799 9282 9393 9892 13027 13900 17031 20491 20817 22113 31175 32797 34960 39303 45082 59024 61232 71444 76524 76759 78974 79799 80672 84250 93166 98041 99492 99604 547 737 1906 1981 4601 5174 8124 12688 15695 17854 18985 19323 19798 23994 24756 26145 26228 26307 26872 27305 3142...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 203ms
memory: 77440kb
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 15 14 23 22 34 33 36 37 48 47 59 57 67 66 73 72 75 74 78 77 99 98 108 107 113 112 128 127 130 131 144 142 148 147 152 151 156 155 162 161 167 165 171 170 180 179 185 183 186 184 193 192 199 198 202 200 207 205 211 210 213 212 215 214 221 220 233 232 245 243 261 260 263 262 267 ...
result:
ok 1000 Cases (1000 test cases)