QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#186111 | #5423. Perfect Matching | _LAP_ | WA | 205ms | 8500kb | C++14 | 1.9kb | 2023-09-23 07:45:19 | 2023-09-23 07:45:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = 2e5 + 10;
int n, A[N], h[N], e[M], ne[M], idx;
inline void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }
inline void add(int a, int b, bool flag) {add(a, b), add(b, a); }
vector<int> lsh;
vector<pair<int, int>> ans;
bool vis[N], used[M];
bool dfs(int u, int fa) { vis[u] = true;
vector<int> E;
for(int i = h[u]; i != -1; i = ne[i]) {
int v = e[i]; if((vis[v] && v != u) || (i ^ 1) == fa) continue;
if(v != u) dfs(v, i); if(!used[i]) used[i] = used[i ^ 1] = true, E.emplace_back(i / 2 + 1);
}
if((int)E.size() % 2 == 1 && fa == -1) return false;
if((int)E.size() % 2 == 1) used[fa] = used[fa ^ 1] = true, E.emplace_back(fa / 2 + 1);
for(int i = 0; i < E.size(); i += 2) ans.push_back({E[i], E[i + 1]});
return true;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
memset(h, -1, sizeof h);
int T; cin >> T;
while(T --) {
cin >> n; memset(h + 1, -1, sizeof(int) * (2 * n)), idx = 0;
lsh.clear(), ans.clear();
memset(used + 1, false, sizeof(bool) * (2 * n)), memset(vis + 1, false, sizeof(bool) * (2 * 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 ++)
add(lower_bound(lsh.begin(), lsh.end(), i - A[i]) - lsh.begin() + 1, lower_bound(lsh.begin(), lsh.end(), i + A[i]) - lsh.begin() + 1, true);
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";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 6048kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 6 3 5 2 4 1 Yes 3 1 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 205ms
memory: 8500kb
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 99962 99957 99954 99939 99927 99921 99896 99893 99890 99872 99870 99863 99849 99836 99830 99825 99819 99804 99795 99791 99788 99774 99771 99752 99750 99741 99723 99720 99716 99714 99710 99707 99699 99693 99686 99668 99659 99657 99642 99632 99630 99627 99617 99609 99596 99578 99572 99566 99...
result:
wrong answer abs(99993-99962) != abs(a[99993]-a[99962]) (test case 1)