QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#733518 | #5423. Perfect Matching | oxcoxsga | AC ✓ | 447ms | 42352kb | C++14 | 2.0kb | 2024-11-10 19:35:55 | 2024-11-10 19:35:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MaxN=1000000;
int n,a[MaxN+1],btr=0;
vector<int>g[MaxN+1];
bool vst[MaxN+1];
vector<pair<int,int>>ans;
pair<vector<int>,bool>DFS(int u,int prt){
vst[u]=true;
vector<int>clt;
for(int v:g[u]){
if(v==prt||vst[v])continue;
auto ret=DFS(v,u);
auto&vec=ret.first;
if(!ret.second)return make_pair(vector<int>(),false);
clt.insert(clt.end(),vec.begin(),vec.end());
}
if(u>n){
while(clt.size()>=2){
ans.emplace_back(clt[clt.size()-1],clt[clt.size()-2]);
clt.pop_back(),clt.pop_back();
}
return make_pair(clt,true);
}else{
if(clt.size()==0){
return make_pair(vector<int>{u},true);
}else if(clt.size()==1){
ans.emplace_back(u,clt.back());
return make_pair(vector<int>(),true);
}else return make_pair(vector<int>(),false);
}
}
void Solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
unordered_map<int,vector<int> >umap;
for(int i=1;i<=n*3;i++)g[i].clear(),vst[i]=false;
ans.clear();
btr=0;
for(int i=1;i<=n;i++)umap[a[i]+i].push_back(i);
for(auto&pi:umap){
if(pi.second.size()<2)continue;
btr++;
//cout<<pi.first<<"(p):";
for(int v:pi.second){
// cout<<v<<' ';
g[btr+n].push_back(v);
g[v].push_back(btr+n);
}
//cout<<'\n';
}
umap.clear();
for(int i=1;i<=n;i++)umap[a[i]-i].push_back(i);
for(auto&pi:umap){
if(pi.second.size()<2)continue;
btr++;
//cout<<pi.first<<"(n):";
for(int v:pi.second){
// cout<<v<<' ';
g[btr+n].push_back(v);
g[v].push_back(btr+n);
}
//cout<<'\n';
}
// cout<<btr<<'\n';
for(int i=1;i<=n;i++){
if(vst[i])continue;
auto ret=DFS(i,0);
if(!ret.second||ret.first.size()){
cout<<"No\n";
return;
}
}
cout<<"Yes\n";
for(auto&pi:ans)cout<<pi.first<<' '<<pi.second<<'\n';
}
/*
1
7
1 4 1 10 1 1 7
*/
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin.tie(0)->sync_with_stdio(false);
int T;
cin>>T;
while(T--)
Solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 28236kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 2 5 3 6 Yes 1 3 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 265ms
memory: 40664kb
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: 4ms
memory: 28408kb
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 8 7 6 5 4 3 1 2 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 9 10 34 33 32 31 29 30 38 37 35 36 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 39 40 68 67 66 65 64 63 62 61 59 60 74 73 72 71 69 70 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 75 76 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 212ms
memory: 38748kb
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 274 273 272 271 270 269 268 267 266 265 264 263 262 261 260 259 258 257 256 255 254 253 252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 ...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 447ms
memory: 42352kb
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 81303 70110 16772 13611 778 34736 73052 62860 56229 35450 80993 88310 74032 11544 940 821 80608 33052 80963 80784 50011 57649 67617 66364 10211 27149 57643 44140 11472 17075 95323 35741 12598 23176 24308 921 92548 81132 83637 41302 28333 92168 3610 71221 37367 7859...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 174ms
memory: 28448kb
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)