QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#648221 | #5423. Perfect Matching | 0x3fffffff | WA | 265ms | 13744kb | C++20 | 2.0kb | 2024-10-17 17:44:09 | 2024-10-17 17:44:12 |
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, -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] != -1) {
ans.push_back({hav[v], i / 2 + 1});
hav[v] = -1;
} else if (hav[u] != -1) {
ans.push_back({hav[u], i / 2 + 1});
hav[u] = -1;
} 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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3564kb
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: 265ms
memory: 13744kb
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)