QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#180279#5423. Perfect MatchingZhou_JKRE 431ms38444kbC++231.9kb2023-09-15 17:46:532023-09-15 17:46:53

Judging History

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

  • [2023-09-15 17:46:53]
  • 评测
  • 测评结果:RE
  • 用时:431ms
  • 内存:38444kb
  • [2023-09-15 17:46:53]
  • 提交

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)
    {
        assert(edge[i]!=edge[i+1]);
        assert(abs(edge[i]-edge[i+1])==abs(a[edge[i]]-a[edge[i+1]]));
        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);
    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()
{
//    freopen("data.in","r",stdin);
//    freopen("data.out","w",stdout); 
    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: 0ms
memory: 8480kb

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: 249ms
memory: 20796kb

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: 3ms
memory: 8176kb

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: 212ms
memory: 38444kb

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: 431ms
memory: 24192kb

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: -100
Dangerous Syscalls

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:


result: