QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#123283#5423. Perfect MatchingGusterBuster27AC ✓2490ms22376kbC++171.4kb2023-07-12 07:00:242023-07-12 07:00:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-12 07:00:25]
  • 评测
  • 测评结果:AC
  • 用时:2490ms
  • 内存:22376kb
  • [2023-07-12 07:00:24]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;

typedef pair<int, int> pii;

map<int, int> pos;
map<int, vector<pii>> edges;
vector<pii> matching;
bool found[MAXN];

int match(int cur) {
	while (pos[cur] < edges[cur].size()) {
		if (found[edges[cur][pos[cur]].second]) {
			pos[cur]++;
			continue;
		}
		int unmatched = edges[cur][pos[cur]].second;
		found[unmatched] = 1;
		int nxt = edges[cur][pos[cur]].first;
		pos[cur]++;
		int v = match(nxt);
		if (v != -1) {
			matching.push_back(pii(v, unmatched));
			unmatched = -1;
		}
		v = match(cur);
		if (v != -1) {
			if (unmatched == -1) unmatched = v;
			else {
				matching.push_back(pii(v, unmatched));
				unmatched = -1;
			}
		}
		return unmatched;
	}
	return -1;
}

void solve() {
	int n; cin >> n;
	pos.clear();
	edges.clear();
	matching.clear();
	fill(found, found+n, 0);
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		edges[2*(x+i)].push_back(pii(2*(x-i)+1, i));
		edges[2*(x-i)+1].push_back(pii(2*(x+i), i));
	}
	for (auto it: edges) pos[it.first] = 0;
	for (auto it: edges) match(it.first);
	assert(2*matching.size() <= n);
	if (2*matching.size() < n) cout << "No\n";
	else {
		cout << "Yes\n";
		for (pii p: matching) cout << p.first+1 << ' ' << p.second+1 << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int t; cin >> t;
	while (t--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3480kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 1072ms
memory: 21424kb

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
99993 99994
99997 99995
99996 99992
99984 99982
99978 99952
99951 99950
99938 99985
99983 99935
99937 99936
99931 99980
99981 99910
99892 99930
99929 99940
99939 99927
99928 99926
99924 99907
99906 99905
99895 99909
99908 99893
99894 99889
99888 99887
99886 99885
99884 99874
99891 99890
99872 99...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 0ms
memory: 3552kb

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
33 32
31 30
29 34
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 100
27 26
25 24
23 22
21 20
19 18
17 16
15 14
13 12
11 10
9 28
67 66
65 64
63 62
61 60
59 68
38 37
36 35
8 7
6 5
4 3
2 1
73 72
71 70
69 74
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 1105ms
memory: 20716kb

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
29351 29350
29349 29348
29347 29346
29345 29344
29343 29342
29341 29340
29339 29338
29337 29336
29335 29334
29333 29332
29331 29330
29329 29352
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: 2490ms
memory: 22376kb

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
89504 28
80864 40225
83793 23486
13417 117
53551 2960
53645 26708
12351 1972
48777 233
56042 48443
63366 39558
46185 4810
63855 31504
95702 73935
96486 58488
85577 660
96471 358
34736 778
57643 44140
17075 11472
92548 81132
63463 26518
8564 1121
3199 1661
73052 62860
56229 35450
70891 8604
67617...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 759ms
memory: 3648kb

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
999 998
992 985
983 996
994 997
1000 995
993 979
981 977
976 970
969 967
953 950
948 946
973 972
971 965
964 959
954 936
944 945
942 939
938 980
978 960
955 934
919 931
932 929
930 928
927 926
911 922
921 915
914 906
894 893
889 888
883 918
917 908
910 905
904 903
902 900
899 9...

result:

ok 1000 Cases (1000 test cases)