QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#186110 | #5423. Perfect Matching | _LAP_ | WA | 197ms | 8372kb | C++14 | 1.9kb | 2023-09-23 07:43:27 | 2023-09-23 07:43:27 |
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] || (i ^ 1) == fa) continue;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4644kb
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: 197ms
memory: 8372kb
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:
No No Yes 99963 99947 99939 99932 99924 99914 99908 99900 99881 99879 99873 99869 99857 99852 99839 99827 99813 99795 99792 99788 99779 99773 99770 99765 99746 99744 99738 99714 99705 99701 99690 99677 99674 99672 99663 99657 99647 99639 99636 99630 99627 99624 99618 99615 99597 99593 99588 99581 99...
result:
wrong answer std outputs a valid answer while participant doesn't (test case 1)