QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#180308#5423. Perfect MatchingZhou_JKAC ✓376ms38556kbC++231.8kb2023-09-15 18:03:022023-09-15 18:03:02

Judging History

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

  • [2023-09-15 18:03:02]
  • 评测
  • 测评结果:AC
  • 用时:376ms
  • 内存:38556kb
  • [2023-09-15 18:03:02]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cassert>
#include<vector>
#include<unordered_map>
using namespace std;
const int N=100005;
const long long INF=4557430888798830399;
int n;
int a[N];
int tot;
vector<pair<long long,int>>G[N*2];
int match[N];
bool vis[N*2];
void dfs(int u,int father,int pre)
{
    vis[u]=true;
    vector<int>edge;
    for(auto [v,i]:G[u])
    {
        if(v==father) continue;
        if(vis[v]) continue;
        dfs(v,u,i);
    }
    for(auto [v,i]:G[u])
        if(i!=pre)
        {
            if(!match[i]) edge.emplace_back(i);
        }
    if(edge.size()%2==1) edge.emplace_back(pre);
    for(int i=0;i<(int)edge.size();i+=2)
        match[edge[i]]=edge[i+1],match[edge[i+1]]=edge[i];
    return;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    unordered_map<int,int>pos;
    tot=0;
    for(int i=1;i<=n;i++)
    {
        if(!pos.count(i-a[i])) pos[i-a[i]]=++tot;
        if(!pos.count(i+a[i]+INF)) pos[i+a[i]+INF]=++tot;
    }
    for(int i=1;i<=tot;i++)
        G[i].clear(),vis[i]=false;
    for(int i=1;i<=n;i++)
        match[i]=0;
    for(int i=1;i<=n;i++)
        G[pos[i-a[i]]].emplace_back(pos[i+a[i]+INF],i),G[pos[i+a[i]+INF]].emplace_back(pos[i-a[i]],i);
    match[0]=0;
    for(int i=1;i<=tot;i++)
        if(!vis[i])
        {
            dfs(i,0,0);
            if(match[0])
            {
                cout<<"No\n";
                return;
            }
        }
    cout<<"Yes\n";
    for(int i=1;i<=n;i++)
        if(i<match[i]) cout<<i<<" "<<match[i]<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 8536kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

Yes
1 4
2 5
3 6
Yes
1 3
2 4
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 255ms
memory: 20668kb

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 100000
2 33
3 79
4 6
5 7
8 9
10 13
11 12
14 15
16 20
17 18
19 26
21 22
23 25
24 99915
27 28
29 31
30 99
32 34
35 59
36 37
38 99908
39 40
41 42
43 45
44 46
47 56
48 49
50 99920
51 52
53 248
54 55
57 58
60 61
62 63
64 65
66 67
68 69
70 71
72 73
74 80
75 76
77 78
81 82
83 84
85 89
86 88
87 97
90 ...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 2ms
memory: 8568kb

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
1 2
3 4
5 6
7 8
9 28
10 11
12 13
14 15
16 17
18 19
20 21
22 23
24 25
26 27
29 34
30 31
32 33
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
59 68
60 61
62 63
64 65
66 67
69 74
70 71
72 73
75 100
76 77
78 79
80 81
82 83
84 85
86 87
88 89
90 91
92 93
94 95
96 97
98 99
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 187ms
memory: 38556kb

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
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
59 60
61 62
63 64
65 66
67 68
69 70
71 72
73 74
75 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
101 ...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 376ms
memory: 24076kb

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
1 4547
2 1932
3 24074
4 9
5 1492
6 140
7 1055
8 97
10 91206
11 449
12 2782
13 14
15 4917
16 7994
17 3227
18 1033
19 405
20 241
21 22355
22 24734
23 24
25 72
26 1088
27 99313
28 89504
29 33
30 97820
31 1158
32 44
34 163
35 82
36 730
37 11617
38 383
39 20594
40 105
41 54113
42 85
43 45
46 1832
47 ...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 169ms
memory: 8868kb

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
1 4
2 8
3 5
6 9
7 999
10 19
11 13
12 988
14 15
16 17
18 21
20 24
22 23
25 27
26 28
29 38
30 39
31 32
33 34
35 42
36 37
40 46
41 43
44 52
45 49
47 48
50 53
51 62
54 58
55 56
57 59
60 63
61 65
64 79
66 67
68 70
69 76
71 83
72 73
74 75
77 78
80 84
81 85
82 86
87 118
88 89
90 96
91...

result:

ok 1000 Cases (1000 test cases)