QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#356901 | #5423. Perfect Matching | Graphcity | AC ✓ | 927ms | 19768kb | C++20 | 1.6kb | 2024-03-18 15:36:41 | 2024-03-18 15:36:42 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e5;
int n,m,a[Maxn+5],dfn[Maxn+5],idx[Maxn+5],anc[Maxn+5];
int cur,vis[Maxn+5],chk[Maxn+5];
map<int,int> mp1,mp2;
vector<pair<int,int>> v[Maxn+5];
inline void Add(int x,int y,int k)
{v[x].emplace_back(y,k),v[y].emplace_back(x,k);}
inline void dfs(int x,int fa)
{
vis[x]=1,dfn[x]=++cur,idx[cur]=x,anc[x]=fa;
for(auto [y,z]:v[x]) if(z!=fa && !vis[y]) dfs(y,z);
}
inline void Clear()
{
For(i,1,m) dfn[i]=idx[i]=anc[i]=vis[i]=0;
For(i,1,n) chk[i]=0;
For(i,1,m) vector<pair<int,int>>().swap(v[i]);
mp1.clear(),mp2.clear(),cur=m=0;
}
inline void Solve()
{
cin>>n;
For(i,1,n) cin>>a[i];
For(i,1,n)
{
if(!mp1.count(a[i]-i)) mp1[a[i]-i]=++m;
if(!mp2.count(a[i]+i)) mp2[a[i]+i]=++m;
Add(mp1[a[i]-i],mp2[a[i]+i],i);
}
For(i,1,m) if(!dfn[i]) dfs(i,0);
vector<pair<int,int>> ans;
Rof(_,m,1)
{
int i=idx[_]; vector<int> w;
for(auto [y,z]:v[i]) if(z!=anc[i] && !chk[z]) w.push_back(z);
if((w.size()&1) && anc[i] && !chk[anc[i]]) w.push_back(anc[i]);
if((w.size()&1)) {puts("No"); Clear(); return;}
int sz=w.size();
for(auto i:w) chk[i]=1;
for(int i=1;i<sz;i+=2) ans.emplace_back(w[i-1],w[i]);
} puts("Yes");
for(auto [a,b]:ans) printf("%d %d\n",a,b); Clear();
}
int main()
{
// freopen("1.in","r",stdin);
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: 0ms
memory: 7852kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 3 6 2 5 4 1 Yes 2 4 3 1 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 415ms
memory: 15212kb
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 99917 99919 99737 99739 99677 99679 99455 99457 99443 99445 99401 99403 99395 99397 99305 99307 99149 99151 99020 99022 99005 99007 98921 98923 98885 98887 98840 98842 98729 98731 98726 98728 98513 98515 98489 98491 98423 98425 98414 98416 98129 98131 98120 98122 98027 98029 98021 98023 97961 97...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 2ms
memory: 7744kb
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 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 70 71 72 73 74 69 60 61 62 63 64 65 66 67 68 59 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 35 36 37 38 30 31 32 33 34 29 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 9 1 2 3 4 5 6 7 8 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 511ms
memory: 19768kb
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 99931 99932 99933 99934 99935 99936 99937 99938 99939 99940 99941 99942 99943 99944 99945 99946 99947 99948 99949 99950 99951 99952 99953 99954 99955 99956 99957 99958 99959 99960 99961 99962 99963 99964 99965 99966 99967 99968 99969 99970 99971 99972 99973 99974 99975 99976 99977 99978 99979 99...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 927ms
memory: 16612kb
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 99218 88939 78074 76238 82959 57705 61980 54401 46385 44951 81600 34575 37350 22885 83312 17128 61118 72253 73378 89878 14355 13478 41948 75220 50307 3921 93196 72221 57485 30932 51271 97884 99029 91807 98270 83582 90844 73668 95199 71535 98865 56881 96333 54765 78203 52006 75907 56391 87749 450...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 309ms
memory: 8036kb
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 973 972 945 944 930 929 922 921 882 881 860 859 847 846 805 804 793 792 779 778 757 756 625 624 577 576 565 564 555 554 549 548 547 546 543 542 540 539 525 524 519 518 484 483 472 471 468 467 462 461 436 435 433 432 428 427 413 412 388 387 385 384 321 320 316 315 308 307 280 27...
result:
ok 1000 Cases (1000 test cases)