QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#186113 | #5423. Perfect Matching | _LAP_ | WA | 212ms | 14400kb | C++14 | 1.9kb | 2023-09-23 08:02:53 | 2023-09-23 08:02:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, A[N]; vector<pair<int, int>> G[N];
vector<int> lsh; vector<pair<int, int>> ans;
bool vis[N], used[N];
bool dfs(int u, int fa) { vis[u] = true;
vector<int> E; int flag = 0;
for(auto &v : G[u]) {
if(v.second == fa) continue;
if(v.first != u) {
if(vis[v.first]) continue;
dfs(v.first, v.second);
if(!used[v.second]) E.emplace_back(v.second);
} else flag = v.second;
}
if(flag) E.emplace_back(flag);
if((int)E.size() % 2 == 1) {
if(fa == -1) return false;
else E.emplace_back(fa);
}
for(int i = 0; i < E.size(); i += 2)
ans.push_back({E[i], E[i + 1]}), used[E[i]] = true, used[E[i + 1]] = true;
return true;
}
inline void solve() {
cin >> n;
for(int i = 1; i <= n; i ++) cin >> A[i];
for(int i = 1; i <= n; i ++) lsh.emplace_back(i - A[i]), lsh.emplace_back(i + A[i]);
sort(lsh.begin(), lsh.end()), lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
for(int i = 1; i <= n; i ++) {
int a = lower_bound(lsh.begin(), lsh.end(), i - A[i]) - lsh.begin() + 1;
int b = lower_bound(lsh.begin(), lsh.end(), i + A[i]) - lsh.begin() + 1;
G[a].push_back({b, i}), G[b].push_back({a, i});
}
bool flag = true;
for(int i = 1; i <= lsh.size(); i ++)
if(!vis[i]) flag = flag && dfs(i, -1);
if(flag) {
cout << "Yes\n";
for(auto &pr : ans) cout << pr.first << ' ' << pr.second << '\n';
} else cout << "No\n";
// roll back
for(int i = 1; i <= lsh.size(); i ++) vis[i] = false;
for(int i = 1; i <= lsh.size(); i ++) G[i].clear();
for(int i = 1; i <= n; i ++) used[i] = false;
lsh.clear(), ans.clear();
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9168kb
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: -100
Wrong Answer
time: 212ms
memory: 14400kb
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 7 31 34 79 100 124 130 139 202 205 226 244 289 292 310 316 322 337 364 373 379 382 391 397 418 436 451 460 463 481 511 517 520 526 556 568 586 619 658 661 667 736 754 763 772 790 808 823 826 853 874 904 925 934 964 970 979 988 1003 1009 1027 1030 1048 1078 1090 1105 1162 1171 1216 1219 1228 1273...
result:
wrong answer abs(130-139) != abs(a[130]-a[139]) (test case 1)