QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#123282#5423. Perfect MatchingGusterBuster27WA 1090ms27356kbC++171.4kb2023-07-12 06:55:042023-07-12 06:55:07

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 06:55:07]
  • 评测
  • 测评结果:WA
  • 用时:1090ms
  • 内存:27356kb
  • [2023-07-12 06:55:04]
  • 提交

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[x+i].push_back(pii(x-i, i));
		edges[x-i].push_back(pii(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: 3400kb

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

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
99981 99980
99997 99995
99999 99998
99996 99992
99991 99990
99989 99987
99984 99982
99978 99988
99986 99979
99977 99975
99973 99972
99971 99976
99974 99968
99970 99969
99967 99994
99993 99966
99965 99964
99961 99963
99962 99957
99958 99956
99953 99952
99951 99950
99948 99959
99960 99946
99945 99...

result:

wrong answer abs(99978-99988) != abs(a[99978]-a[99988]) (test case 1)