QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#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;
}
详细
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)