QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#123282 | #5423. Perfect Matching | GusterBuster27 | WA | 1090ms | 27356kb | C++17 | 1.4kb | 2023-07-12 06:55:04 | 2023-07-12 06:55:07 |
Judging History
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)