QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#588288#5423. Perfect Matchingship2077AC ✓402ms32852kbC++231.5kb2024-09-25 09:07:042024-09-25 09:07:05

Judging History

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

  • [2024-09-25 09:07:05]
  • 评测
  • 测评结果:AC
  • 用时:402ms
  • 内存:32852kb
  • [2024-09-25 09:07:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int M=4e5+5;
bool vis[M],flag[M];
int n,num,x[M],y[M],lsh[M],dep[M];
vector<pair<int,int>>ans,adj[M];
int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
    return x*f;
}
void dfs(int x,int f){
    vis[x]=1;int tmp=0;
    for (auto [y,z]:adj[x]){
        if (z==f) continue;
        if (!vis[y]) dep[y]=dep[x]+1,dfs(y,z);
        if (dep[y]>dep[x]){
            if (flag[z]) continue;
            if (!tmp) {tmp=z;continue;}
            ans.emplace_back(tmp,z);flag[tmp]=flag[z]=1;tmp=0;
        }
    }
    if (tmp&&f) ans.emplace_back(tmp,f),flag[tmp]=flag[f]=1;
}
void solve(){
    n=read();num=0;ans.clear();
    for (int i=1;i<=n;i++)
        x[i]=read(),y[i]=x[i]+i,x[i]-=i,
        lsh[++num]=x[i],lsh[++num]=y[i];
    sort(lsh+1,lsh+num+1);num=unique(lsh+1,lsh+num+1)-lsh-1;
    for (int i=1;i<=num<<1;i++) adj[i].clear(),vis[i]=0;
    for (int i=1;i<=n;i++) flag[i]=0;
    for (int i=1;i<=n;i++)
        x[i]=lower_bound(lsh+1,lsh+num+1,x[i])-lsh,
        y[i]=lower_bound(lsh+1,lsh+num+1,y[i])-lsh,
        adj[x[i]].emplace_back(y[i]+num,i),
        adj[y[i]+num].emplace_back(x[i],i);
    for (int i=1;i<=num<<1;i++)
        if (!vis[i]) dep[i]=0,dfs(i,0);
    if (ans.size()!=n/2) return puts("No"),void();
    puts("Yes");
    for (auto [x,y]:ans) printf("%d %d\n",x,y);
}
int main(){int T=read();while (T--) solve();return 0;}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 217ms
memory: 23268kb

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
14 15
16 20
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 ...

result:

ok 10 Cases (10 test cases)

Test #3:

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

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
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
35 36
37 38
1 2
3 4
5 6
7 8
69 70
71 72
73 74
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 200ms
memory: 32852kb

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

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 402ms
memory: 19148kb

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
8564 26518
63463 1121
36817 129
8931 95315
89504 28
70110 81303
13611 16772
34736 778
11544 74032
88310 80993
33052 80608
3199 1661
47380 3633
3408 19162
59542 87006
97729 416
62860 73052
35450 56229
55641 9450
99552 2005
84101 4926
81132 92548
8961 29263
41302 83637
11086 16914
92168 28333
7122...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 138ms
memory: 8120kb

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
14 20
3 5
26 28
29 38
41 43
45 49
57 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...

result:

ok 1000 Cases (1000 test cases)