QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#662142#5423. Perfect MatchingAndycraftAC ✓450ms38440kbC++202.2kb2024-10-20 21:24:372024-10-20 21:24:38

Judging History

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

  • [2024-10-20 21:24:38]
  • 评测
  • 测评结果:AC
  • 用时:450ms
  • 内存:38440kb
  • [2024-10-20 21:24:37]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
template <class T> using Arr = std::vector<T>;

struct edge_t {
	int to, id;
};

const int MAXN = 100002;
int n, a[MAXN];
Arr<edge_t> e[MAXN * 2], tr[MAXN * 2];
int vis[MAXN * 2], fa[MAXN * 2], fa_id[MAXN * 2], sz[MAXN * 2], out[MAXN * 2];

void add(int u, int v, int w) {
	// printf("add %d %d %d\n", u, v, w);
	e[u].push_back({v, w});
	e[v].push_back({u, w});
}

bool mark[MAXN];
Arr<std::pair<int, int>> ans;
void connect(int u, int v) {
	assert(!mark[u] && !mark[v]);
	ans.push_back({u, v});
	mark[u] = mark[v] = true;
}

bool fail;

void dfs(int p) {
	sz[p] = 1, vis[p] = true;
	for (auto [to, _] : e[p])
		if (to != fa[p] && !vis[to]) {
			fa[to] = p;
			fa_id[to] = _;
			tr[p].push_back({to, _});
			dfs(to);
			sz[p] += sz[to];
		}

	int tmp = 0, last;
	for (auto [to, id] : e[p])
		if (fa[p] != to && !mark[id]) {
			tmp++;
			if (tmp & 1) {
				last = id;
			} else {
				connect(last, id);
			}
		}
	if (tmp & 1) {
		if (~fa_id[p])
			connect(last, fa_id[p]);
		else
			fail = true;
	}
}

void Solve() {
	std::cin >> n;
	Arr<int> ls, rs;
	for (int i = 1; i <= n; ++i) {
		std::cin >> a[i];
		ls.push_back(i - a[i]);
		rs.push_back(i + a[i]);
	}
	std::sort(ls.begin(), ls.end());
	ls.erase(std::unique(ls.begin(), ls.end()), ls.end());
	std::sort(rs.begin(), rs.end());
	rs.erase(std::unique(rs.begin(), rs.end()), rs.end());
	int ln = (int)ls.size(), rn = (int)rs.size();
	auto find = [](Arr<int> &v, int x) { return (int)(std::lower_bound(v.begin(), v.end(), x) - v.begin()); };

	for (int i = 0; i < ln + rn; ++i) {
		e[i].clear(), tr[i].clear();
		vis[i] = false;
		fa[i] = fa_id[i] = -1;
		sz[i] = 0;
		out[i] = -1;
	}
	for (int i = 1; i <= n; ++i)
		mark[i] = false;

	for (int i = 1; i <= n; ++i) {
		int l = find(ls, i - a[i]);
		int r = find(rs, i + a[i]);
		add(l, ln + r, i);
	}

	ans.clear();
	fail = false;
	for (int i = 0; i < ln + rn; ++i)
		if (!vis[i]) {
			dfs(i);
			if (fail)
				return puts("No"), void();
		}
	assert(ans.size() == n / 2);
	puts("Yes");
	for (auto [u, v] : ans)
		printf("%d %d\n", u, v);
}

int main() {
	std::ios::sync_with_stdio(false);
	int T;
	std::cin >> T;
	while (T--)
		Solve();
	return 0;
}

详细

Test #1:

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

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 246ms
memory: 21280kb

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
21 22
77 78
137 138
200 201
242 244
287 289
308 309
314 315
320 321
335 337
380 382
395 396
449 450
458 459
461 462
479 480
515 517
518 520
524 526
554 556
566 567
617 619
659 660
734 736
761 763
788 790
851 853
902 903
932 933
977 978
986 987
1088 1089
1103 1104
1160 1162
1217 1218
1271 1273
12...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 2ms
memory: 6104kb

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 216ms
memory: 38440kb

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
49559 49560
29353 29354
29355 29356
29357 29358
29359 29360
29361 29362
29363 29364
29365 29366
29367 29368
29369 29370
29371 29372
29373 29374
29375 29376
29377 29378
29379 29380
29381 29382
29383 29384
29385 29386
29387 29388
29389 29390
29391 29392
29393 29394
29395 29396
29397 29398
33954 33...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 450ms
memory: 25812kb

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
8564 26518
63463 1121
36811 36817
8931 95315
96991 61541
70110 81303
13611 16772
34736 778
88310 80993
821 11544
74032 940
33052 80608
9050 10585
78597 37367
41232 65442
84943 50244
91157 52881
5417 10333
18933 19162
3408 59542
87006 97729
79681 23980
27149 66364
67617 10211
17075 44140...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 149ms
memory: 5948kb

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
14 15
57 59
66 67
77 78
98 99
129 130
142 144
161 162
165 167
183 185
184 186
198 199
200 202
205 207
214 215
232 233
243 245
270 271
279 280
284 286
307 308
312 314
315 316
320 321
328 330
332 333
370 372
384 385
387 388
412 413
421 422
424 426
427 428
432 433
435 436
440 442
...

result:

ok 1000 Cases (1000 test cases)