QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#561932 | #5423. Perfect Matching | louhao088 | AC ✓ | 431ms | 28044kb | C++17 | 2.8kb | 2024-09-13 13:17:24 | 2024-09-13 13:17:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int re, zf; char C;
int read() {
re = 0; zf = 1;
C = getchar();
while (C < '0' || C > '9') {
if (C == '-') zf = -zf;
C = getchar();
}
while (C >= '0' && C <= '9') {
re = re * 10 + C - '0';
C = getchar();
}
return re * zf;
}
const int N = 3e5 + 100;
int n, a[N], b[N], c[N];
int bb[N], cc[N], du[N];
struct node {
int x, to, nxt;
}e[N];
int le[N], KK;
void add(int x, int y, int i) {
e[++KK] = (node){i, y, le[x]}; le[x] = KK;
e[++KK] = (node){i, x, le[y]}; le[y] = KK;
}
vector <int> ans[N];
bool in[N], ind[N];
int dfs0(int now, int father) {
int re = 0; ind[now] = 1;
for (int i = le[now]; i; i = e[i].nxt) {
if (now < e[i].to) re++;
if (!ind[e[i].to]) {
re += dfs0(e[i].to, e[i].x);
}
}
int num = 0;
for (int i = le[now]; i; i = e[i].nxt)
if (!in[e[i].x] && e[i].x != father) {
num++; ans[now].push_back(e[i].x); in[e[i].x] = 1;
}
// cout << now << " " << num << endl;
if (num & 1) {
in[father] = 1; ans[now].push_back(father);
}
return re;
}
void slove() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = a[i] - i; c[i] = a[i] + i;
bb[i] = b[i]; cc[i] = c[i];
}
sort(bb + 1, bb + n + 1); sort(cc + 1, cc + n + 1);
int bn = unique(bb + 1, bb + n + 1) - bb - 1, cn = unique(cc + 1, cc + n + 1) - cc - 1;
for (int i = 1; i <= n; i++) {
b[i] = lower_bound(bb + 1, bb + bn + 1, b[i]) - bb;
}
for (int i = 1; i <= n; i++) {
c[i] = lower_bound(cc + 1, cc + cn + 1, c[i]) - cc + bn;
}
for (int i = 1; i <= n; i++) add(b[i], c[i], i);
for (int i = 1; i <= n; i++) in[i] = 0;
for (int i = 1; i <= bn + cn; i++) ind[i] = 0;
bool yes = 1;
// cout << "bn=" << bn << " cn=" << cn << endl;
for (int i = 1; i <= bn + cn; i++)
if (!ind[i]) {
if (dfs0(i, 0) & 1) {
yes = 0; break;
}
}
for (int i = 1; i <= bn + cn; i++) {
if (ans[i].size() & 1) {
yes = 0; break;
}
}
if (yes) {
printf("Yes\n");
for (int i = 1; i <= bn + cn; i++) {
for (int j = 0; j + 1 < ans[i].size(); j += 2)
printf("%d %d\n", ans[i][j], ans[i][j + 1]);
}
}
else {
printf("No\n");
}
for (int i = 1; i <= bn + cn; i++) du[i] = 0, ans[i].clear();
for (int i = 1; i <= n; i++) in[i] = 0;
for (int i = 1; i <= bn + cn; i++) le[i] = 0; KK = 0;
}
int main()
{
int t = read();
while (t--) slove();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 22264kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 5 2 6 3 1 4 Yes 4 2 1 3 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 249ms
memory: 26396kb
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 99986 99988 99976 99974 99970 99968 99965 99966 99963 99962 99959 99960 99958 99957 99955 99954 99949 99947 99945 99946 99933 99934 99922 99920 99917 99919 99916 99914 99912 99913 99904 99902 99897 99896 99882 99881 99880 99878 99875 99876 99854 99855 99837 99836 99835 99833 99826 99825 99820 99...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 20520kb
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 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 8 7 6 5 4 3 2 1 33 32 31 30 29 34 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 100 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 28 67 66 65 64 63 62 61 60 59 68 73 72 71 70 69 74 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 202ms
memory: 28044kb
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 72010 72009 72008 72007 72006 72005 72004 72003 72002 72001 72000 71999 71998 71997 71996 71995 71994 71993 71992 71991 71990 71989 71988 71987 71986 71985 71984 71983 71982 71981 71980 71979 71978 71977 71976 71975 71974 71973 71972 71971 71970 71969 71968 71967 71966 71965 71964 71963 71962 71...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 431ms
memory: 25100kb
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 99702 99327 98613 99642 99730 99113 97548 98113 98679 97655 96859 96855 96806 96932 99263 97303 97988 99210 96812 99635 96532 98341 99893 99141 97709 96335 96360 96278 95800 97243 96046 95828 97927 95341 95658 95569 94839 95591 97589 99387 94779 94620 96102 95615 98529 94051 96718 95835 94792 94...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 155ms
memory: 20316kb
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 997 994 977 976 970 969 967 953 950 948 946 942 939 938 928 927 926 911 905 904 903 902 900 899 887 872 868 855 853 848 844 832 830 821 819 816 814 801 796 794 780 772 760 759 754 741 729 722 707 696 695 691 686 681 678 675 667 666 662 657 655 644 643 642 639 637 635 634 632 62...
result:
ok 1000 Cases (1000 test cases)