QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#561932#5423. Perfect Matchinglouhao088AC ✓431ms28044kbC++172.8kb2024-09-13 13:17:242024-09-13 13:17:25

Judging History

你现在查看的是最新测评结果

  • [2024-09-13 13:17:25]
  • 评测
  • 测评结果:AC
  • 用时:431ms
  • 内存:28044kb
  • [2024-09-13 13:17:24]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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)