QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#724873 | #5423. Perfect Matching | Erinyes | WA | 956ms | 30036kb | C++14 | 1.2kb | 2024-11-08 15:25:03 | 2024-11-08 15:25:03 |
Judging History
answer
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=3e5+5;
int n,tot,cnt;
int a[N],vst[N],del[N];
map<int,int>A,B;
vector<int>son[N];
vector<pair<int,int>>ans;
void dfs(int x,int fa){
vst[x]=1,cnt+=x<=n;
vector<int> d;
for(int y:son[x]){
if(!vst[y]){
dfs(y,x);
if(x>n&&!del[y])d.push_back(y);
}
}
if(x>n){
for(int i=0;i+1<d.size();i+=2)ans.push_back({d[i],d[i+1]});
if(d.size()&1){
if(fa&&!del[fa])ans.push_back({d.back(),fa}),del[fa]=1;
}
}
}
inline void solve(){
cin>>n,tot=n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(A.find(a[i]+i)==A.end())A[a[i]+i]=++tot;
if(B.find(a[i]-i)==B.end())B[a[i]-i]=++tot;
son[i].push_back({A[a[i]+i]}),son[A[a[i]+i]].push_back(i);
son[i].push_back({B[a[i]-i]}),son[B[a[i]-i]].push_back(i);
}
for(int i=1;i<=tot;i++){
if(vst[i])continue;
cnt=0,dfs(i,0);
if(cnt&1)return cout<<"No\n",void();
}
cout<<"Yes\n";
for(auto t:ans)cout<<t.first<<' '<<t.second<<endl;
for(int i=1;i<=tot;i++)son[i].clear(),vst[i]=del[i]=0;
ans.clear(),A.clear(),B.clear();
}
signed main(){
#ifndef ONLINE_JUDGE
freopen(".in","r",stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
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: 3ms
memory: 12676kb
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: 377ms
memory: 23452kb
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 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 1283 128...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 3ms
memory: 12624kb
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 3 4 5 6 7 8 1 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 9 30 31 32 33 34 29 36 37 38 35 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 39 60 61 62 63 64 65 66 67 68 59 70 71 72 73 74 69 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 75 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 411ms
memory: 30036kb
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 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 10...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 956ms
memory: 27248kb
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 8564 26518 63463 1121 70110 81303 13611 16772 34736 778 62860 73052 35450 56229 88310 80993 821 11544 74032 940 33052 80608 80784 80963 57649 50011 27149 66364 67617 10211 17075 44140 57643 11472 23176 35741 95323 12598 921 24308 81132 92548 41302 83637 92168 28333 71221 3610 78597 3736...
result:
ok 10 Cases (10 test cases)
Test #6:
score: -100
Wrong Answer
time: 225ms
memory: 13036kb
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 Yes 29 27 37 35 55 53 9 8 48 47 57 56 59 58 64 65 89 90 92 93 115 116 119 120 122 121 129 130 134 136 140 141 151 150 162 163 168 169 185 184 187 186 190 189 191 192 216 218 219 220 221 222 229 230 237 236 244 245 249 250 269 268 274 273 284 285 316 317 320 322 361 360 365 364 379 378 418 419 ...
result:
wrong answer abs(37-35) != abs(a[37]-a[35]) (test case 3)