QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#771828#5423. Perfect Matchingcyc001AC ✓979ms31772kbC++232.6kb2024-11-22 15:53:512024-11-22 15:53:52

Judging History

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

  • [2024-11-22 15:53:52]
  • 评测
  • 测评结果:AC
  • 用时:979ms
  • 内存:31772kb
  • [2024-11-22 15:53:51]
  • 提交

answer

#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
#define fcin cin
#define fcout cout
class tree{
private:
    vector<vector<pair<int,int>>> gr;
    vector<int> id;
    vector<int> sum,siz,vis;
    auto dfs(int u,int fr=-1)->void{
        sum[u]=siz[u];vis[u]=true;
        for(auto&[v,w]:gr[u]) if(!vis[v]){
            dfs(v,u);sum[u]+=(sum[v]-1);
            if(sum[v]&1) id[w]=u;
            else id[w]=v;
        }else if(v!=fr&&id[w]==-1){
            --sum[u];id[w]=v;
        }
    }
public:
    auto link(int u,int v,int w){
        gr[u].emplace_back(v,w);
        gr[v].emplace_back(u,w);
    }
    auto setsiz(vector<int> _siz){siz=_siz;}
    auto check(){
        cir(i,0,(int)(gr.size())) if(!vis[i]) dfs(i);
        return id;
    }
    tree(int _n,int _m):gr(_n),id(_m,-1),sum(_n),siz(_n),vis(_n){}
};
class dsu{
private:
    vector<int> f,siz;
public:
    auto findset(int u)->int{
        return f[u]==u?u:f[u]=findset(f[u]);
    }
    auto merge(int u,int v){
        u=findset(u);v=findset(v);
        if(u==v) return;
        f[u]=v;siz[v]+=siz[u];
    }
    auto size(auto u){return siz[findset(u)];}
    dsu(int _n):f(_n),siz(_n,1){iota(f.begin(),f.end(),0);}
};
int main(){
    ios::sync_with_stdio(false),fcin.tie(nullptr);
    int T;fcin>>T;
    while(T--) []{
        int n;fcin>>n;vector<int> a(n);
        for(auto&i:a) fcin>>i;
        map<int,vector<int>> ax,bx;
        cir(i,0,n) ax[a[i]-i].push_back(i);
        cir(i,0,n) bx[a[i]+i].push_back(i);
        vector<vector<int>> fr(n);
        dsu ds(n);
        auto cccnt=-1;
        vector<int> siz;
        for(auto&[a,b]:ax){
            ++cccnt;
            for(auto&i:b) fr[i].push_back(cccnt);
            cir(i,1,(int)(b.size())) ds.merge(b[i-1],b[i]);
            siz.push_back(b.size());
        }
        for(auto&[a,b]:bx){
            ++cccnt;
            for(auto&i:b) fr[i].push_back(cccnt);
            cir(i,1,(int)(b.size())) ds.merge(b[i-1],b[i]);
            siz.push_back(b.size());
        }
        auto vaild=true;
        cir(i,0,n) vaild&=(!(ds.size(i)&1));
        if(!vaild) return fcout<<"No"<<'\n',void();
        tree tr(cccnt+1,n);
        cir(i,0,n) tr.link(fr[i][0],fr[i][1],i);
        tr.setsiz(siz);
        const auto id=tr.check();
        map<int,vector<int>> idx;
        cir(i,0,n) idx[id[i]].push_back(i);
        fcout<<"Yes"<<'\n';
        for(auto&[a,b]:idx){
            for(auto i=0;i<(int)(b.size());i+=2) fcout<<b[i]+1<<' '<<b[i+1]+1<<'\n';
        }
    }();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 350ms
memory: 26536kb

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
140 142
34 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
2...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3860kb

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
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
35 36
37 38
1 2
3 4
5 6
7 8
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
69 70
71 72
73 74
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 344ms
memory: 31772kb

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
71753 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
71779 71780
71781 71782
71783 71784
71785 71786
71787 71788
71789 71790
71791 71792
71793 71794
71795 71796
71797 71798
71799 71800
71801 71...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 979ms
memory: 29672kb

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
99327 99702
97303 99263
98626 98946
95828 96046
95341 97927
97343 98426
97616 97711
95342 98589
93465 99602
93214 96560
93180 97318
92136 96630
94719 95270
94735 96521
93661 95654
92554 97683
92059 92301
97337 97522
90752 94744
91889 93560
93095 95731
91882 96890
97295 98433
90174 92734
95536 97...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 262ms
memory: 3868kb

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
2 8
10 15
19 44
52 59
60 63
67 78
80 84
95 97
99 100
115 117
131 140
144 162
167 168
185 186
189 196
197 199
202 206
207 209
215 216
217 218
233 234
238 239
245 247
248 253
258 264
265 272
280 281
286 290
305 308
314 316
321 322
327 330
334 353
360 362
369 372
379 380
385 388
4...

result:

ok 1000 Cases (1000 test cases)