QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#356901#5423. Perfect MatchingGraphcityAC ✓927ms19768kbC++201.6kb2024-03-18 15:36:412024-03-18 15:36:42

Judging History

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

  • [2024-03-18 15:36:42]
  • 评测
  • 测评结果:AC
  • 用时:927ms
  • 内存:19768kb
  • [2024-03-18 15:36:41]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e5;

int n,m,a[Maxn+5],dfn[Maxn+5],idx[Maxn+5],anc[Maxn+5];
int cur,vis[Maxn+5],chk[Maxn+5];
map<int,int> mp1,mp2;
vector<pair<int,int>> v[Maxn+5];
inline void Add(int x,int y,int k)
{v[x].emplace_back(y,k),v[y].emplace_back(x,k);}
inline void dfs(int x,int fa)
{
    vis[x]=1,dfn[x]=++cur,idx[cur]=x,anc[x]=fa;
    for(auto [y,z]:v[x]) if(z!=fa && !vis[y]) dfs(y,z);
}
inline void Clear()
{
    For(i,1,m) dfn[i]=idx[i]=anc[i]=vis[i]=0;
    For(i,1,n) chk[i]=0;
    For(i,1,m) vector<pair<int,int>>().swap(v[i]);
    mp1.clear(),mp2.clear(),cur=m=0;
}
inline void Solve()
{
    cin>>n;
    For(i,1,n) cin>>a[i];
    For(i,1,n)
    {
        if(!mp1.count(a[i]-i)) mp1[a[i]-i]=++m;
        if(!mp2.count(a[i]+i)) mp2[a[i]+i]=++m;
        Add(mp1[a[i]-i],mp2[a[i]+i],i);
    }
    For(i,1,m) if(!dfn[i]) dfs(i,0);
    vector<pair<int,int>> ans;
    Rof(_,m,1)
    {
        int i=idx[_]; vector<int> w;
        for(auto [y,z]:v[i]) if(z!=anc[i] && !chk[z]) w.push_back(z);
        if((w.size()&1) && anc[i] && !chk[anc[i]]) w.push_back(anc[i]);
        if((w.size()&1)) {puts("No"); Clear(); return;}
        int sz=w.size();
        for(auto i:w) chk[i]=1;
        for(int i=1;i<sz;i+=2) ans.emplace_back(w[i-1],w[i]);
    } puts("Yes");
    for(auto [a,b]:ans) printf("%d %d\n",a,b); Clear();
}

int main()
{
    // freopen("1.in","r",stdin);

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

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 415ms
memory: 15212kb

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
99917 99919
99737 99739
99677 99679
99455 99457
99443 99445
99401 99403
99395 99397
99305 99307
99149 99151
99020 99022
99005 99007
98921 98923
98885 98887
98840 98842
98729 98731
98726 98728
98513 98515
98489 98491
98423 98425
98414 98416
98129 98131
98120 98122
98027 98029
98021 98023
97961 97...

result:

ok 10 Cases (10 test cases)

Test #3:

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

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 511ms
memory: 19768kb

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
99931 99932
99933 99934
99935 99936
99937 99938
99939 99940
99941 99942
99943 99944
99945 99946
99947 99948
99949 99950
99951 99952
99953 99954
99955 99956
99957 99958
99959 99960
99961 99962
99963 99964
99965 99966
99967 99968
99969 99970
99971 99972
99973 99974
99975 99976
99977 99978
99979 99...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 927ms
memory: 16612kb

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
99218 88939
78074 76238
82959 57705
61980 54401
46385 44951
81600 34575
37350 22885
83312 17128
61118 72253
73378 89878
14355 13478
41948 75220
50307 3921
93196 72221
57485 30932
51271 97884
99029 91807
98270 83582
90844 73668
95199 71535
98865 56881
96333 54765
78203 52006
75907 56391
87749 450...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 309ms
memory: 8036kb

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
973 972
945 944
930 929
922 921
882 881
860 859
847 846
805 804
793 792
779 778
757 756
625 624
577 576
565 564
555 554
549 548
547 546
543 542
540 539
525 524
519 518
484 483
472 471
468 467
462 461
436 435
433 432
428 427
413 412
388 387
385 384
321 320
316 315
308 307
280 27...

result:

ok 1000 Cases (1000 test cases)