QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#186130 | #5423. Perfect Matching | _LAP_ | AC ✓ | 552ms | 124080kb | C++14 | 2.4kb | 2023-09-23 08:54:56 | 2023-09-23 08:54:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
int n, A[N]; vector<int> E[N]; vector<pair<int, int>> G[N];
vector<long long> lsh; vector<pair<int, int>> ans;
bool vis[N], used[N];
int dep[N], fa[N]; vector<int> vec;
void dfs(int u, int Fa) {
vis[u] = true, fa[u] = Fa, dep[u] = dep[Fa] + 1; vec.emplace_back(u);
for(auto &v : G[u])
if(!vis[v.first]) dfs(v.first, u);
}
inline void solve() {
cin >> 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] + INF);
sort(lsh.begin(), lsh.end()), lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
for(int i = 1; i <= n; i ++) {
int a = lower_bound(lsh.begin(), lsh.end(), i - A[i]) - lsh.begin() + 1;
int b = lower_bound(lsh.begin(), lsh.end(), i + A[i] + INF) - lsh.begin() + 1;
if(a == b) E[a].emplace_back(i);
else G[a].push_back({b, i}), G[b].push_back({a, i});
}
bool flag = true;
for(int i = 1; i <= lsh.size(); i ++) if(!vis[i]) {
vec.clear(); dfs(i, 0); sort(vec.begin(), vec.end(), [](int a, int b) {return dep[a] > dep[b]; });
for(auto &u : vec) {
for(auto &v : G[u]) {
if(v.first == fa[u]) continue;
if(!used[v.second]) E[u].emplace_back(v.second);
}
if((int)E[u].size() % 2 == 1) {
if(fa[u] == 0) {flag = false; break; }
else E[u].emplace_back((lsh[u - 1] + lsh[fa[u] - 1] - INF) / 2), assert((lsh[u - 1] + lsh[fa[u] - 1] - INF) % 2 == 0);
}
for(int j = 0; j < E[u].size(); j += 2)
assert((!used[E[u][j]]) && (!used[E[u][j + 1]])), used[E[u][j]] = used[E[u][j + 1]] = true, ans.push_back({E[u][j], E[u][j + 1]});
}
if(!flag) break;
}
if(flag) {
cout << "Yes\n";
for(auto &pr : ans) cout << pr.first << ' ' << pr.second << '\n';
} else cout << "No\n";
for(int i = 1; i <= lsh.size(); i ++) vis[i] = false;
for(int i = 1; i <= n; i ++) used[i] = false;
for(int i = 1; i <= lsh.size(); i ++) E[i].clear(), G[i].clear();
lsh.clear(), ans.clear();
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 99720kb
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: 286ms
memory: 115964kb
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 41079 41080 44703 44704 48193 48191 41950 41948 43984 43982 45654 45655 39778 39776 49803 49804 44377 44375 47508 47509 42711 42712 43509 43510 46336 46334 41578 41576 48726 48727 40402 40400 45264 45265 44946 44947 50550 50551 44448 44449 47922 47923 44152 44150 49528 49526 43756 43754 47178 47...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 16ms
memory: 97688kb
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: 237ms
memory: 124080kb
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: 552ms
memory: 112768kb
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 9775 16810 64517 64903 59285 67547 8534 68382 71199 13877 85146 89511 70149 29137 85560 81341 88879 97785 75540 87133 22008 85079 8303 44517 72263 89557 61627 82684 83843 84773 99556 49026 24525 83355 10990 79957 51117 77752 3313 8502 74867 24403 56526 83458 72637 94022 26324 37926 27644 42552 4...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 181ms
memory: 97808kb
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 648 650 683 685 687 689 690 692 736 738 746 748 539 540 542 543 546 547 548 549 554 555 557 559 564 565 576 577 578 580 608 609 615 617 624 625 884 885 890 892 907 909 908 910 921 922 881 882 929 930 944 945 756 757 778 779 792 793 804 805 824 826 839 840 846 847 859 860 142 14...
result:
ok 1000 Cases (1000 test cases)