QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#78151#5423. Perfect MatchingJinTianHaoAC ✓494ms24020kbC++172.4kb2023-02-17 09:30:162023-02-17 09:30:19

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-17 09:30:19]
  • 评测
  • 测评结果:AC
  • 用时:494ms
  • 内存:24020kb
  • [2023-02-17 09:30:16]
  • 提交

answer

#include <bits/stdc++.h>
#define inf 1000000007
#define mod 1000000007
// #define int long long
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
template <typename T> void write(T x) {
	if (x<0) x=-x,putchar('-');
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n,a[100005],ed;
vector<int> numsl,numsr;
vector<pair<int,int>> g[200005];
int vis[200005],match[100005];
void dfs1(int x)
{
	vis[x]=1;
	ed+=g[x].size();
	for(auto i:g[x])
		if(!vis[i.first])
			dfs1(i.first);
}
void dfs2(int x,int fa)
{
	vis[x]=2;
	vector<int> vec;
	int tofa;
	for(auto i:g[x])
		if(i.first==fa) tofa=i.second;
		else if(vis[i.first]!=2) dfs2(i.first,x);
	for(auto i:g[x])
		if(i.first!=fa&&!match[i.second])
			vec.push_back(i.second);
	if(vec.size()&1) vec.push_back(tofa);
	for(int i=0;i<vec.size();i+=2)
		match[vec[i]]=vec[i+1],match[vec[i+1]]=vec[i];
}
signed main()
{
	// freopen("accepts.in","r",stdin);
	// freopen("accepts.out","w",stdout);
	int tc;read(tc);
	while(tc--)
	{
		read(n);
		numsl.clear();
		numsr.clear();
		for(int i=1;i<=n;++i)
		{
			read(a[i]);match[i]=0;
			numsl.push_back(i-a[i]);
			numsr.push_back(i+a[i]);
		}
		sort(numsl.begin(),numsl.end());
		numsl.erase(unique(numsl.begin(),numsl.end()),numsl.end());
		sort(numsr.begin(),numsr.end());
		numsr.erase(unique(numsr.begin(),numsr.end()),numsr.end());
		for(int i=1;i<=numsl.size()+numsr.size();++i)
			g[i].clear(),vis[i]=0;
		for(int i=1;i<=n;++i)
		{
			int x=upper_bound(numsl.begin(),numsl.end(),i-a[i])-numsl.begin();
			int y=upper_bound(numsr.begin(),numsr.end(),i+a[i])-numsr.begin()+numsl.size();
			g[x].push_back({y,i});
			g[y].push_back({x,i});
		}
		bool flag=1;
		for(int i=1;i<=numsl.size()+numsr.size();++i)
			if(!vis[i])
			{
				ed=0;dfs1(i);ed/=2;
				if(ed&1)
				{
					flag=0;break;
				}
				dfs2(i,0);
			}
		if(!flag) puts("No");
		else
		{
			puts("Yes");
			for(int i=1;i<=n;++i) vis[i]=0;
			for(int i=1;i<=n;++i)
				if(!vis[i]) write(i),putchar(' '),writeln(match[i]),vis[i]=vis[match[i]]=1;
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 8200kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

Yes
1 4
2 5
3 6
Yes
1 3
2 4
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 259ms
memory: 18324kb

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
1 100000
2 33
3 79
4 6
5 7
8 9
10 13
11 12
14 15
16 20
17 18
19 26
21 22
23 25
24 99915
27 28
29 31
30 99
32 34
35 59
36 37
38 99908
39 40
41 42
43 45
44 46
47 56
48 49
50 99920
51 52
53 248
54 55
57 58
60 61
62 63
64 65
66 67
68 69
70 71
72 73
74 80
75 76
77 78
81 82
83 84
85 89
86 88
87 97
90 ...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 4ms
memory: 8088kb

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
1 2
3 4
5 6
7 8
9 28
10 11
12 13
14 15
16 17
18 19
20 21
22 23
24 25
26 27
29 34
30 31
32 33
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
59 68
60 61
62 63
64 65
66 67
69 74
70 71
72 73
75 100
76 77
78 79
80 81
82 83
84 85
86 87
88 89
90 91
92 93
94 95
96 97
98 99
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 223ms
memory: 24020kb

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
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
59 60
61 62
63 64
65 66
67 68
69 70
71 72
73 74
75 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
101 ...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 494ms
memory: 18460kb

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
1 4547
2 1932
3 24074
4 9
5 1492
6 140
7 1055
8 97
10 91206
11 449
12 2782
13 14
15 4917
16 7994
17 3227
18 1033
19 405
20 241
21 22355
22 24734
23 24
25 72
26 1088
27 99313
28 89504
29 33
30 97820
31 1158
32 44
34 163
35 82
36 730
37 11617
38 383
39 20594
40 105
41 54113
42 85
43 45
46 1832
47 ...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 151ms
memory: 8224kb

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
1 4
2 10
3 5
6 9
7 20
8 997
11 30
12 16
13 991
14 15
17 18
19 44
21 25
22 23
24 55
26 28
27 31
29 38
32 35
33 34
36 37
39 40
41 43
42 51
45 49
46 50
47 48
52 60
53 54
56 61
57 59
58 69
62 64
63 80
65 81
66 67
68 70
71 83
72 73
74 75
76 88
77 78
79 82
84 95
85 91
86 90
87 118
89...

result:

ok 1000 Cases (1000 test cases)