QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#648233 | #5423. Perfect Matching | 0x3fffffff | WA | 293ms | 13640kb | C++20 | 2.0kb | 2024-10-17 17:47:58 | 2024-10-17 17:48:02 |
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>v;
for (int i = 1; i <= n; i++) {
cin >> a[i];
v.push_back(i - a[i]);
v.push_back(i + a[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int m = v.size() + 5;
vector<vector<int>>h(m + 1);
vector<array<int, 2>>e;
vector<int>vis(m + 1), hav(m + 1), pp(m * 4 + 10,1);
auto add = [&](int a, int b) {
h[a].push_back(e.size());
e.push_back({a, b});
};
for (int i = 1; i <= n; i++) {
int x = lower_bound(v.begin(), v.end(), i - a[i]) - v.begin() + 1;
int y = lower_bound(v.begin(), v.end(), i + a[i]) - v.begin() + 1;
add(x, y);
add(y, 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 <= v.size(); 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: 3572kb
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: 293ms
memory: 13640kb
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 1 11 21 22 5 7 12 30 29 31 32 33 3 34 77 78 98 99 79 100 122 123 128 129 124 130 137 138 200 201 139 202 203 205 224 225 242 244 287 289 290 291 226 292 308 309 314 315 310 316 320 321 335 337 362 364 371 372 322 373 377 378 380 382 389 391 395 396 379 397 416 417 434 435 418 436 449 450 458 459...
result:
wrong answer abs(79-100) != abs(a[79]-a[100]) (test case 1)