QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#662123#5423. Perfect MatchingAndycraftWA 197ms22284kbC++202.0kb2024-10-20 21:13:422024-10-20 21:13:42

Judging History

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

  • [2024-10-20 21:13:42]
  • 评测
  • 测评结果:WA
  • 用时:197ms
  • 内存:22284kb
  • [2024-10-20 21:13:42]
  • 提交

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], 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});
}

Arr<std::pair<int, int>> ans;
void connect(int u, int v) {
	ans.push_back({u, v});
}

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

	int tmp = 0, last;
	for (auto [to, id] : tr[p]) {
		if (sz[to] & 1) {
			++tmp;
			if (tmp & 1)
				last = id;
			else
				connect(id, last);
		} else
			connect(id, out[to]);
	}
	if (tmp & 1)
		out[p] = last;
	assert((tmp & 1) != (sz[p] & 1));
}

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] = -1;
		sz[i] = 0;
		out[i] = -1;
	}

	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 (~sz[i] & 1)
				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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 197ms
memory: 22284kb

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
139 79
244 202
310 289
322 316
382 337
451 397
463 460
517 481
526 520
568 556
661 619
763 736
853 790
934 904
988 979
1105 1090
1219 1162
1285 1273
1405 1294
1456 1411
1531 1459
1561 1555
1615 1588
1630 1618
1669 1651
1723 1684
1915 1738
2026 1972
2092 2029
2197 2155
2305 2290
2353 2350
2431 24...

result:

wrong output format Expected integer, but "Yes" found (test case 1)