QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#648300 | #5423. Perfect Matching | 0x3fffffff | RE | 1ms | 3592kb | C++20 | 2.3kb | 2024-10-17 18:11:15 | 2024-10-17 18:11:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
void solve() {
int n; cin >> n;
vector<int>a(n + 1);
vector<int>v1,v2;
for (int i = 1; i <= n; i++) {
cin >> a[i];
v1.push_back(i - a[i]);
v2.push_back(i + a[i]);
}
sort(v1.begin(), v1.end());
v1.erase(unique(v1.begin(), v1.end()), v1.end());
sort(v2.begin(), v2.end());
v2.erase(unique(v2.begin(), v2.end()), v2.end());
int m1 = v1.size();
int m2 = v2.size();
// for(auto x:v1){
// cout<<x<<" ";
// }
// cout<<"\n";
int m=m1+m2;
vector<vector<int>>h(m + 1);
vector<array<int, 2>>e;
vector<int>vis(m + 1), hav(m + 1), pp(m * 2 + 10, 1);
auto add = [&](int a, int b) {
// cout<<a<<" "<<b<<"\n";
h[a].push_back(e.size());
e.push_back({a, b});
};
for (int i = 1; i <= n; i++) {
int x = lower_bound(v1.begin(), v1.end(), i - a[i]) - v1.begin() + 1;
int y = lower_bound(v2.begin(), v2.end(), i + a[i]) - v2.begin() + 1;
// cout<<x<<" "<<y<<"\n";
add(x, y+m1);
add(y+m1, x);
}
vector<array<int, 2>>ans;
auto dfs = [&](auto && ff, int u, int lst)->void{
vis[u] = 1;
for (int i : h[u]) {
int v = e[i][1];
int ok = pp[i];
pp[i] = pp[i ^ 1] = 0;
if (ok) {
if (!vis[v] and i != (lst ^ 1)) {
ff(ff, v, 0);
}
if (hav[v]) {
ans.push_back({hav[v], i / 2 + 1});
hav[v] = 0;
} else if (hav[u] ) {
ans.push_back({hav[u], i / 2 + 1});
hav[u] = 0;
} else {
hav[u] = i / 2 + 1;
}
}
}
};
for (int i = 1; i <=m; i++) {
if (!vis[i])dfs(dfs, i, -1);
}
// cout<<ans.size()<<"\n";
if ((int)ans.size() == 0 || (int)ans.size() * 2 != n) {
cout << "No\n";
return;
}
cout << "Yes\n";
for (auto [u, v] : ans) {
cout << u << " " << v << "\n";
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt = 1;
cin >> tt;
while (tt--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3592kb
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
Runtime Error
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...