QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91732 | #5423. Perfect Matching | Wolam | AC ✓ | 488ms | 13008kb | C++14 | 1.8kb | 2023-03-29 14:50:57 | 2023-03-29 14:51:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005],b[2][100005];
int vis[400005],head[200005],tot;
int h[400005];
struct ss{
int node,nxt;
}e[400005];
void add(int u,int v)
{
e[++tot].nxt=head[u];
e[tot].node=v;
head[u]=tot;
}
pair<int,int> ans[100005];
int len;
void dfs(int x,int fa)
{
// cerr<<x<<endl;
int now=0;
int f=0;
h[x]=1;
for(int i=head[x];i;i=e[i].nxt)
{
if(vis[i])continue;
int y=e[i].node;
if(y==fa)
{
f=i;
continue;
}
if(!h[y])
dfs(y,x);
if(vis[i])continue;
if(now)
{
ans[++len]=make_pair(now>>1,i>>1);
vis[i]=vis[i^1]=vis[now]=vis[now^1]=1;
now=0;
}
else now=i;
}
if(now&&f)
{
// cerr<<x<<" "<<now<<" "<<f<<" "<<vis[now]<<" "<<vis[f]<<endl;
ans[++len]=make_pair(now>>1,f>>1);
vis[now]=vis[now^1]=vis[f]=vis[f^1]=1;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
// scanf("%d",&T);
while(T--)
{
cin>>n;
tot=1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[0][i]=i+a[i];
b[1][i]=i-a[i];
}
sort(b[0]+1,b[0]+n+1);
sort(b[1]+1,b[1]+n+1);
b[0][0]=unique(b[0]+1,b[0]+n+1)-b[0]-1;
b[1][0]=unique(b[1]+1,b[1]+n+1)-b[1]-1;
for(int i=1;i<=b[0][0]+b[1][0];i++)
h[i]=head[i]=0;
for(int i=1;i<=n;i++)
{
int x=lower_bound(b[0]+1,b[0]+b[0][0]+1,a[i]+i)-b[0];
int y=lower_bound(b[1]+1,b[1]+b[1][0]+1,i-a[i])-b[1];
// cerr<<x<<" "<<y<<endl;
add(x,y+b[0][0]);add(y+b[0][0],x);
}
for(int i=1;i<=tot;i++)
vis[i]=0;
len=0;
for(int i=1;i<=b[0][0]+b[1][0];i++)
if(!h[i])dfs(i,0);
// if(n==100000)cout<<tot<<" "<<len<<endl;
if(len==n/2)
{
cout<<"Yes\n";
for(int i=1;i<=len;i++)
cout<<ans[i].first<<" "<<ans[i].second<<'\n';
}
else cout<<"No\n";
}
}
/*
1
3 18 33
UDRLR
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7532kb
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 4 2 3 1 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 265ms
memory: 12540kb
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 100000 99999 99998 99991 99990 99989 99974 99976 99987 99975 99973 99972 99968 99970 99971 99969 99959 99960 99945 99946 99933 99934 99917 99919 99882 99881 99765 99764 99883 99766 99759 99758 99737 99739 99690 99689 99760 99691 99677 99679 99663 99662 99651 99650 99664 99652 99576 99575 99558 9...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 9764kb
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 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 34 33 32 31 30 29 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 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 68 67 66 65 64 63 62 61 60 59 38 37 36 35 8 7 6 5 4 3 2 1 74 73 72 71 70 69 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 254ms
memory: 11252kb
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 29352 29351 29350 29349 29348 29347 29346 29345 29344 29343 29342 29341 29340 29339 29338 29337 29336 29335 29334 29333 29332 29331 29330 29329 72010 72009 72008 72007 72006 72005 72004 72003 72002 72001 72000 71999 71998 71997 71996 71995 71994 71993 71992 71991 71990 71989 71988 71987 71986 71...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 488ms
memory: 13008kb
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 99604 99492 95645 91596 85466 84947 82692 81449 87276 72615 85017 64132 99137 92808 99746 93927 98836 97748 79587 76223 75405 71176 96783 95546 71578 42197 82241 82064 95716 94006 92758 87144 86775 86089 95018 90292 96405 38165 98496 86372 75387 52229 89930 51424 72714 64229 83039 60060 93907 59...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 159ms
memory: 11812kb
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 987 986 988 982 963 962 968 961 958 957 952 951 941 935 913 912 933 901 898 897 896 879 875 866 858 857 862 856 852 843 833 823 811 810 809 808 803 799 795 785 783 777 775 774 771 770 769 767 761 758 755 752 740 739 747 737 728 727 721 720 719 718 730 715 705 704 706 703 702 70...
result:
ok 1000 Cases (1000 test cases)