QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91732#5423. Perfect MatchingWolamAC ✓488ms13008kbC++141.8kb2023-03-29 14:50:572023-03-29 14:51:00

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-29 14:51:00]
  • 评测
  • 测评结果:AC
  • 用时:488ms
  • 内存:13008kb
  • [2023-03-29 14:50:57]
  • 提交

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)