QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#394193 | #5423. Perfect Matching | marher | AC ✓ | 530ms | 10524kb | C++14 | 1.5kb | 2024-04-20 10:01:36 | 2024-04-20 10:01:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50;
struct edge
{
int u,v,nxt,w,p;
}e[N];
int T,n,a[N],wa[N],wb[N],ma,mb,head[N],cnt=1,vis[N];
vector<pair<int,int>>ans;
void clear()
{
for(int i=1;i<=ma+mb;i++)head[i]=vis[i]=0;
cnt=1;vector<pair<int,int>>().swap(ans);
}
void add(int u,int v,int w)
{
// cout<<u<<' '<<v<<' '<<w<<'\n';
e[++cnt]=(edge){u,v,head[u],w,0};head[u]=cnt;
e[++cnt]=(edge){v,u,head[v],w,0};head[v]=cnt;
}
void ad(int x,int y)
{
ans.push_back(make_pair(e[x].w,e[y].w));
}
int dfs(int x,int fid)
{
// cout<<"DFS "<<x<<'\n';
int la=0;vis[x]=1;
for(int i=head[x];i;i=e[i].nxt)if(!e[i].p)
{
e[i].p=e[i^1].p=1;
int w=0;
if(!vis[e[i].v])w=dfs(e[i].v,i);
if(w)continue;
if(!la)la=i;else ad(la,i),la=0;
}
if(la)ad(la,fid);
// cout<<x<<' '<<fid<<' '<<la<<'\n';
return la!=0;
}
void sol()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)wa[i]=i-a[i],wb[i]=i+a[i];
sort(wa+1,wa+1+n);ma=unique(wa+1,wa+1+n)-wa-1;
sort(wb+1,wb+1+n);mb=unique(wb+1,wb+1+n)-wb-1;
for(int i=1;i<=n;i++)add(lower_bound(wa+1,wa+1+ma,i-a[i])-wa,lower_bound(wb+1,wb+1+mb,i+a[i])-wb+ma,i);
for(int i=1;i<=ma;i++)if(!vis[i]&&dfs(i,-1))
{
puts("No");
return;
}
puts("Yes");
for(auto x:ans)cout<<x.first<<' '<<x.second<<'\n';
}
main()
{
// freopen("in.txt","r",stdin);
cin>>T;
while(T--)sol(),clear();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3716kb
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 4 1 Yes 3 1 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 348ms
memory: 9584kb
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 99977 99979 99821 99823 99980 99981 99929 99930 99994 99993 99940 99939 99928 99927 99894 99893 99892 99891 99873 99872 99871 99869 99890 99870 99864 99863 99850 99849 99831 99830 99796 99794 99792 99791 99790 99789 99795 99788 99772 99770 99754 99753 99771 99752 99751 99750 99724 99722 99718 99...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3648kb
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 70 69 8 7 6 5 4 3 2 1 38 37 36 35 68 67 66 65 64 63 62 61 60 59 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 34 33 32 31 30 29 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: 390ms
memory: 9844kb
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: 530ms
memory: 10524kb
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 99509 99438 99574 89492 85048 82608 95716 94006 92758 87144 86775 86089 95018 90292 96405 38165 98496 86372 75387 52229 89930 51424 72714 64229 83039 60060 93907 59825 90797 40204 84293 82260 81601 68474 98409 66518 90682 86864 63426 23563 97115 55593 98299 86138 81768 79940 78538 71812 70984 66...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 215ms
memory: 3744kb
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 979 981 978 980 994 977 999 998 996 992 985 983 971 965 964 959 945 944 954 936 931 932 930 929 922 921 917 918 915 914 906 894 893 889 886 884 888 885 882 881 883 880 878 877 876 873 860 859 861 849 847 846 845 842 841 839 840 838 837 812 805 804 797 798 793 792 790 791 802 78...
result:
ok 1000 Cases (1000 test cases)