QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#208992#5423. Perfect Matchingucup-team870AC ✓314ms27932kbC++171.5kb2023-10-09 23:38:252023-10-09 23:38:25

Judging History

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

  • [2023-10-09 23:38:25]
  • 评测
  • 测评结果:AC
  • 用时:314ms
  • 内存:27932kb
  • [2023-10-09 23:38:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define P pair<int,int>
#define ll long long
#define vi vector<int>
const int N=2e5+5;
P ans[N]; int top=0;
vector<P>tu[N];
unordered_map<int,int>mp1,mp2;
int dep[N];
int dfs(int now,int pre){
    dep[now]=dep[pre]+1;
    vi q;
    for(auto [son,id]:tu[now]){
        if(son==pre)continue;
        if(dep[son]){
            if(dep[son]>dep[now])q.push_back(id);
            continue;
        }
        int res=dfs(son,now);
        if(res)ans[++top]={id,res};
        else q.push_back(id);
    }
    int res=0;
    if(q.size()&1)res=q.back(),q.pop_back();
    for(int i=0;i<q.size();i+=2){
        ans[++top]={q[i],q[i+1]};
    }
    return res;
}
void slv(){
    mp1.clear(); mp2.clear();
    int n;cin>>n;
    vi a(n+1);
    rep(i,1,n){
        cin>>a[i]; mp1[a[i]-i]=1; mp2[a[i]+i]=1;
    }
    int cnt=0;
    for(auto &[_,v]:mp1)v=++cnt;
    for(auto &[_,v]:mp2)v=++cnt;
    rep(i,1,cnt)tu[i].clear(),dep[i]=0;
    rep(i,1,n){
        int u=mp1[a[i]-i],v=mp2[a[i]+i];
        tu[u].push_back({v,i}); tu[v].push_back({u,i});
    }
    top=0;
    rep(i,1,cnt){
        if(dep[i])continue;
        if(dfs(i,0)){
            cout<<"No\n";return;
        }
    }
    cout<<"Yes\n";
    rep(i,1,top)cout<<ans[i].first<<' '<<ans[i].second<<'\n';
}
signed main(){
    IOS
    int T;cin>>T;
    while(T--)slv();
}

详细

Test #1:

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

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 191ms
memory: 24500kb

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: 2ms
memory: 8892kb

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
75 76
77 78
79 80
81 82
83 84
85 86
87 88
89 90
91 92
93 94
95 96
97 98
100 99
29 30
31 32
34 33
35 36
37 38
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
28 27
69 70
71 72
74 73
1 2
3 4
5 6
7 8
59 60
61 62
64 65
66 67
63 68
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 167ms
memory: 27932kb

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: 314ms
memory: 21840kb

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
70110 81303
13611 16772
778 34736
55231 92637
3408 19162
59542 87006
416 97729
81132 92548
41302 83637
28333 92168
3610 71221
80993 88310
11544 74032
33052 80608
14756 42619
1661 3199
3633 47380
26691 37677
27149 66364
10211 67617
1...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 145ms
memory: 8452kb

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
3 5
26 28
29 36
38 41
43 45
49 68
70 71
74 83
87 112
118 119
122 124
126 129
134 139
141 142
143 146
151 165
170 175
177 178
183 184
200 203
205 208
212 219
220 226
243 257
266 268
270 273
274 277
284 285
298 300
312 313
323 324
326 328
332 335
339 345
354 359
361 365
366 370
3...

result:

ok 1000 Cases (1000 test cases)