QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#759576#5423. Perfect MatchingwangchunjieAC ✓874ms42252kbC++141.5kb2024-11-18 10:12:032024-11-18 10:12:04

Judging History

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

  • [2024-11-18 10:12:04]
  • 评测
  • 测评结果:AC
  • 用时:874ms
  • 内存:42252kb
  • [2024-11-18 10:12:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=2e5+5;

int T,n,a[N],dep[N];
map<int,int> x,y;
vector<pair<int,int>> ans,G[N];

int dfs(int u,int pa)
{
    dep[u]=dep[pa]+1;
    vector<int> vec;
    for(auto i:G[u]){
        int v=i.first,id=i.second;
        if(v==pa) continue;
        if(dep[v]){
            if(dep[v]>dep[u])
                vec.emplace_back(id);
            continue;
        }
        int res=dfs(v,u);
        if(res) ans.emplace_back(id,res);
        else vec.emplace_back(id);
    }
    int res=0;
    if(vec.size()&1) res=vec.back(),vec.pop_back();
    for(int i=0;i<vec.size();i+=2)
        ans.emplace_back(vec[i],vec[i+1]);
    return res;
}

void solve()
{
    x.clear(),y.clear(),ans.clear();
    memset(dep,0,sizeof(dep));
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        x[a[i]+i]=1,y[a[i]-i]=1;
    int cnt=0;
    for(auto &i:x) i.second=++cnt;
    for(auto &i:y) i.second=++cnt;
    for(int i=1;i<=cnt;i++)
        G[i].clear();
    for(int i=1;i<=n;i++){
        int u=x[a[i]+i],v=y[a[i]-i];
        G[u].emplace_back(v,i);
        G[v].emplace_back(u,i);
    }
    for(int i=1;i<=cnt;i++){
        if(dep[i]) continue;
        if(dfs(i,0))
            return cout<<"No\n",void();
    }
    cout<<"Yes\n";
    for(auto i:ans)
        cout<<i.first<<' '<<i.second<<'\n';
}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
2 4
1 3
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 332ms
memory: 31032kb

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
79 139
202 244
289 310
316 322
337 382
397 451
460 463
481 517
520 526
556 568
619 661
736 763
790 853
904 934
979 988
1090 1105
1162 1219
1273 1285
1294 1405
1411 1456
1459 1531
1555 1561
1588 1615
1618 1630
1651 1669
1684 1723
1738 1915
1972 2026
2029 2092
2155 2197
2290 2305
2350 2353
2419 24...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 0ms
memory: 10544kb

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 328ms
memory: 42252kb

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
29329 29330
29331 29332
29333 29334
29335 29336
29337 29338
29339 29340
29341 29342
29343 29344
29345 29346
29347 29348
29349 29350
29351 29352
71754 71755
71756 71757
71758 71759
71760 71761
71762 71763
71764 71765
71766 71767
71768 71769
71770 71771
71772 71773
71774 71775
71776 71777
71778 71...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 874ms
memory: 29972kb

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
28 89504
8564 26518
1121 63463
129 36817
8931 95315
61541 96991
81132 92548
41302 83637
778 34736
4360 12537
2005 99552
92893 97953
30631 58176
19622 70597
26691 37677
27149 66364
10211 67617
17075 44140
11472 57643
23176 35741
12598 95323
28519 68565
10746 21782
47710 63141
67911 89833
19087 80...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 237ms
memory: 10292kb

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
6 9
16 17
18 21
22 25
27 31
32 33
35 42
47 51
62 64
72 79
82 86
90 96
101 103
107 109
111 121
127 145
147 155
157 159
164 166
169 174
176 179
191 192
195 201
204 210
223 229
230 237
244 246
252 260
262 269
276 282
292 293
294 295
296 297
301 303
304 306
309 318
325 329
336 338
...

result:

ok 1000 Cases (1000 test cases)