QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#744698 | #5423. Perfect Matching | DengDuck | AC ✓ | 352ms | 67232kb | C++14 | 1.4kb | 2024-11-13 22:54:19 | 2024-11-13 22:54:23 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+5;
int n,A[N],Flg,D[N];
vector<int>L,R;
unordered_map<int,int>Ma[2];
struct Edge{int v,Id;};
vector<Edge>E[N],Ans;
int Dfs(int u,int f,int Lst)
{
D[u]=D[f]+1;
vector<int>e;
for(Edge i:E[u])
{
if(i.v==f)continue;
if(D[i.v])
{
if(D[i.v]<D[u])e.pb(i.Id);
}
else
{
int K=Dfs(i.v,u,i.Id);
if(K!=-1)e.pb(K);
}
}
while(e.size()>1)
{
int x=e.back();e.pop_back();
int y=e.back();e.pop_back();
Ans.pb({x,y});
}
if(e.size())
{
if(Lst==-1)Flg=0;
Ans.pb({Lst,e.back()});
return -1;
}
return Lst;
}
inline void Work()
{
L.clear(),R.clear();
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
L.pb(i-A[i]),R.pb(i+A[i]);
}
sort(L.begin(),L.end()),sort(R.begin(),R.end());
L.erase(unique(L.begin(),L.end()),L.end());
R.erase(unique(R.begin(),R.end()),R.end());
int m1=L.size(),m2=R.size();
for(int i=0;i<m1;i++)Ma[0][L[i]]=i;
for(int i=0;i<m2;i++)Ma[1][R[i]]=i;
for(int i=0;i<m1+m2;i++)E[i].clear();
for(int i=1;i<=n;i++)
{
int l=Ma[0][i-A[i]],r=m1+Ma[1][i+A[i]];
E[l].pb({r,i}),E[r].pb({l,i});
}
Flg=1,Ans.clear();
memset(D,0,sizeof(D));
for(int i=0;i<m1+m2;i++)if(!D[i])Dfs(i,0,-1);
if(!Flg)return puts("No"),void();
puts("Yes");
for(Edge i:Ans)printf("%d %d\n",i.v,i.Id);
}
int main()
{
int T;scanf("%d",&T);
while(T--)Work();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9220kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 6 3 5 2 1 4 Yes 1 3 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 226ms
memory: 27144kb
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 22 21 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 12...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 9524kb
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 74 73 72 71 69 70 8 7 6 5 4 3 2 1 38 37 36 35 68 67 66 65 64 63 62 61 59 60 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 9 10 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 34 33 32 31 29 30 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 212ms
memory: 67232kb
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 49560 49559 29398 29397 29396 29395 29394 29393 29392 29391 29390 29389 29388 29387 29386 29385 29384 29383 29382 29381 29380 29379 29378 29377 29376 29375 29374 29373 29372 29371 29370 29369 29368 29367 29366 29365 29364 29363 29362 29361 29360 29359 29358 29357 29356 29355 29354 29353 34124 34...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 352ms
memory: 27032kb
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 81303 70110 16772 13611 778 34736 80993 88310 74032 11544 940 821 80608 33052 10585 9050 37367 78597 84943 65442 50244 41232 52881 91157 10333 5417 19162 18933 97729 87006 59542 3408 23980 79681 67617 66364 10211 27149 57643 44140...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 118ms
memory: 9724kb
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 59 57 67 66 78 77 99 98 130 129 144 142 162 161 167 165 185 183 186 184 199 198 202 200 207 205 215 214 233 232 245 243 271 270 280 279 286 284 308 307 314 312 316 315 321 320 330 328 333 332 372 370 385 384 388 387 413 412 422 421 426 424 428 427 433 432 436 435 442 440 ...
result:
ok 1000 Cases (1000 test cases)