QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#180276#5423. Perfect MatchingZhou_JKWA 376ms38476kbC++231.8kb2023-09-15 17:45:162023-09-15 17:45:16

Judging History

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

  • [2023-09-15 17:45:16]
  • 评测
  • 测评结果:WA
  • 用时:376ms
  • 内存:38476kb
  • [2023-09-15 17:45:16]
  • 提交

answer

#include<iostream>
#include<cstdio>
#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);
    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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 8404kb

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: 268ms
memory: 20532kb

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: 8332kb

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: 196ms
memory: 38476kb

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: 24232kb

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
Wrong Answer
time: 145ms
memory: 8832kb

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
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

wrong answer std outputs a valid answer while participant doesn't (test case 7)