QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387887#5423. Perfect Matchingwsc2008#AC ✓1112ms60336kbC++141.9kb2024-04-12 22:53:572024-04-12 22:53:57

Judging History

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

  • [2024-04-12 22:53:57]
  • 评测
  • 测评结果:AC
  • 用时:1112ms
  • 内存:60336kb
  • [2024-04-12 22:53:57]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=1e6+9;
ll T,n,a[N],tot,dep[N];
vector<pii>to[N],ans;
map<ll,ll>mp1,mp2;
ll dfs(ll x,ll f){
    dep[x]=dep[f]+1;
    vector<ll>e;
    for(pii es:to[x]){
        ll y=es.first,id=es.second;
        if(!dep[y]){
            ll ret=dfs(y,x);
            if(ret)ans.push_back(make_pair(ret,id));
            else e.push_back(id);
        }
        else if(dep[y]>dep[x])e.push_back(id);
    }
    rep(i,0,(ll)e.size()-2){
        ans.push_back(make_pair(e[i],e[i+1]));
        i++;
    }
    if((ll)e.size()&1)return e.back();
    return 0;
}
void solve(){
    n=read();
    rep(i,1,n)a[i]=read();
    tot=0;
    mp1.clear(),mp2.clear();
    rep(i,1,n){
        if(!mp1.count(a[i]-i))mp1[a[i]-i]=++tot;
        if(!mp2.count(a[i]+i))mp2[a[i]+i]=++tot;
    }
    rep(i,0,tot+1)to[i].clear();
    rep(i,1,n){
        to[mp1[a[i]-i]].push_back(make_pair(mp2[a[i]+i],i));
        to[mp2[a[i]+i]].push_back(make_pair(mp1[a[i]-i],i));
    }
    rep(i,0,tot+1)dep[i]=0;
    ans.clear();
    rep(i,1,tot){
        if(!dep[i])dfs(i,0);
    }
    if((ll)ans.size()!=n/2)return puts("No"),void();
    puts("Yes");
    for(pii p:ans)write(p.first),putchar(' '),write(p.second),putchar('\n');
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    T=read();
    while(T--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 27412kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 375ms
memory: 43088kb

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

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 395ms
memory: 60336kb

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

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 1112ms
memory: 46404kb

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
89504 28
8564 26518
63463 1121
36817 129
8931 95315
96991 61541
70110 81303
13611 16772
34736 778
88310 80993
11544 74032
33052 80608
78597 37367
65442 84943
50244 20961
91157 52881
10333 6609
3408 19162
59542 87006
97729 416
79681 23980
27149 66364
67617 10211
17075 44140
57643 11472
33046 1885...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 209ms
memory: 27568kb

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)