QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#123283 | #5423. Perfect Matching | GusterBuster27 | AC ✓ | 2490ms | 22376kb | C++17 | 1.4kb | 2023-07-12 07:00:24 | 2023-07-12 07:00:25 |
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[2*(x+i)].push_back(pii(2*(x-i)+1, i));
edges[2*(x-i)+1].push_back(pii(2*(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: 3480kb
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: 0
Accepted
time: 1072ms
memory: 21424kb
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 99993 99994 99997 99995 99996 99992 99984 99982 99978 99952 99951 99950 99938 99985 99983 99935 99937 99936 99931 99980 99981 99910 99892 99930 99929 99940 99939 99927 99928 99926 99924 99907 99906 99905 99895 99909 99908 99893 99894 99889 99888 99887 99886 99885 99884 99874 99891 99890 99872 99...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3552kb
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 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 33 32 31 30 29 34 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 100 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 28 67 66 65 64 63 62 61 60 59 68 38 37 36 35 8 7 6 5 4 3 2 1 73 72 71 70 69 74 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 1105ms
memory: 20716kb
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 29351 29350 29349 29348 29347 29346 29345 29344 29343 29342 29341 29340 29339 29338 29337 29336 29335 29334 29333 29332 29331 29330 29329 29352 72010 72009 72008 72007 72006 72005 72004 72003 72002 72001 72000 71999 71998 71997 71996 71995 71994 71993 71992 71991 71990 71989 71988 71987 71986 71...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 2490ms
memory: 22376kb
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 80864 40225 83793 23486 13417 117 53551 2960 53645 26708 12351 1972 48777 233 56042 48443 63366 39558 46185 4810 63855 31504 95702 73935 96486 58488 85577 660 96471 358 34736 778 57643 44140 17075 11472 92548 81132 63463 26518 8564 1121 3199 1661 73052 62860 56229 35450 70891 8604 67617...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 759ms
memory: 3648kb
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 999 998 992 985 983 996 994 997 1000 995 993 979 981 977 976 970 969 967 953 950 948 946 973 972 971 965 964 959 954 936 944 945 942 939 938 980 978 960 955 934 919 931 932 929 930 928 927 926 911 922 921 915 914 906 894 893 889 888 883 918 917 908 910 905 904 903 902 900 899 9...
result:
ok 1000 Cases (1000 test cases)