QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#662141#5423. Perfect MatchingAndycraftWA 480ms38352kbC++202.2kb2024-10-20 21:24:092024-10-20 21:24:10

Judging History

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

  • [2024-10-20 21:24:10]
  • 评测
  • 测评结果:WA
  • 用时:480ms
  • 内存:38352kb
  • [2024-10-20 21:24:09]
  • 提交

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();
	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: 0ms
memory: 8192kb

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: 217ms
memory: 21548kb

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: 5884kb

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: 218ms
memory: 38352kb

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: 480ms
memory: 24140kb

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: -100
Wrong Answer
time: 128ms
memory: 5876kb

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
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

wrong answer std outputs a valid answer while participant doesn't (test case 7)