QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#648302 | #5423. Perfect Matching | 0x3fffffff | AC ✓ | 515ms | 16952kb | C++20 | 2.3kb | 2024-10-17 18:12:35 | 2024-10-17 18:12:37 |
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 + 10);
vector<array<int, 2>>e;
vector<int>vis(m + 10), hav(m + 10), pp(m * 4 + 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: 0ms
memory: 3644kb
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: 0
Accepted
time: 256ms
memory: 14204kb
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 21 22 77 78 3 79 137 138 200 201 139 202 242 244 287 289 308 309 314 315 310 316 320 321 335 337 380 382 395 396 322 397 449 450 458 459 451 460 461 462 479 480 463 481 515 517 518 520 524 526 554 556 566 567 617 619 659 660 568 661 734 736 761 763 788 790 851 853 902 903 932 933 904 934 977 978...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
10 100 28761184 28761185 28761186 28761187 28761188 28761189 28761190 28761191 -20675012 -20675013 -20675014 -20675015 -20675016 -20675017 -20675018 -20675019 -20675020 -20675021 -20675022 -20675023 -20675024 -20675025 -20675026 -20675027 -20675028 -20675029 -20675030 -20675031 -36758138 -36758139 -...
output:
Yes 70 71 72 73 74 69 1 2 3 4 5 6 7 8 35 36 37 38 60 61 62 63 64 65 66 67 68 59 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 9 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 75 30 31 32 33 34 29 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 226ms
memory: 16952kb
input:
10 100000 -40608960 -40608959 -40608958 -40608957 -40608956 -40608955 -40608954 -40608953 -40608952 -40608951 -40608950 -40608949 -40608948 -40608947 -40608946 -40608945 -40608944 -40608943 -40608942 -40608941 -40608940 -40608939 -40608938 -40608937 -40608936 -40608935 -40608934 -40608933 -40608932 ...
output:
Yes 49559 49560 29353 29354 29355 29356 29357 29358 29359 29360 29361 29362 29363 29364 29365 29366 29367 29368 29369 29370 29371 29372 29373 29374 29375 29376 29377 29378 29379 29380 29381 29382 29383 29384 29385 29386 29387 29388 29389 29390 29391 29392 29393 29394 29395 29396 29397 29398 33954 33...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 515ms
memory: 15896kb
input:
10 100000 0 -1 -2 3 2 5 6 7 -2 1 0 9 12 11 -8 13 8 -7 16 17 -10 19 22 21 22 23 4 -15 -18 -17 -6 -31 -14 25 32 -25 26 27 -32 31 38 -31 -32 -19 -30 -35 46 45 -48 -37 48 41 46 -43 -44 53 56 55 50 -27 52 61 62 -33 -18 19 64 45 46 -57 -8 -25 -26 -11 -22 49 -66 -65 -66 29 78 -15 74 83 12 83 14 85 86 -7 -5...
output:
Yes 13 14 89504 28 6 29 49 54 4 15 57 58 8564 26518 63463 1121 61 522 153 222 36811 36817 84 129 8931 95315 506 7625 42 87 536 1600 96991 61541 47 48 99 152 25 124 70110 81303 13611 16772 7 323 126 132 34736 778 62 7528 52 1672 859 1003 92 127 262 768 66 118 50 1549 8 476 288 2392 51 454 317 332 122...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 190ms
memory: 3760kb
input:
1000 1000 -2 0 3 4 6 7 4 7 6 9 11 9 10 12 16 13 16 17 18 20 19 19 24 22 25 23 28 25 26 27 30 32 31 34 36 37 34 37 37 40 42 43 44 45 43 44 46 45 50 48 51 49 54 55 52 55 54 57 56 61 60 61 64 65 64 67 65 66 67 68 71 73 73 75 76 77 78 75 76 78 82 79 80 81 83 83 87 88 90 89 90 93 92 93 95 94 96 96 100 97...
output:
No No No No No No Yes 3 5 26 28 2 10 14 15 19 44 29 57 52 59 60 63 66 67 77 78 80 84 95 97 98 99 100 115 129 130 117 131 142 144 161 162 165 167 140 168 183 185 184 186 189 196 198 199 200 202 197 206 205 207 214 215 209 216 217 218 232 233 234 238 243 245 239 247 248 253 258 264 270 271 265 272 279...
result:
ok 1000 Cases (1000 test cases)