QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#732275#5423. Perfect MatchingJoeyJAC ✓781ms40836kbC++143.0kb2024-11-10 13:51:092024-11-10 13:51:10

Judging History

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

  • [2024-11-10 13:51:10]
  • 评测
  • 测评结果:AC
  • 用时:781ms
  • 内存:40836kb
  • [2024-11-10 13:51:09]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define ssiz(x) (signed)x.size()
#define allc(x) x.begin(),x.end()
const int N=2e5+9;

int a[N],u[N],v[N],r[N],ans[N],n,tot;
vector<pair<int,int>> e[N];
vector<int> tmp[N];

int vis[N],c[N],root;
void DFS(int x){
    vis[x]=1;
    for(auto p:e[x]){
        int y=p.first;
        if(!vis[y]){
            c[y]=c[x]^1;
            DFS(y);
        }else if(c[y]==c[x]) root=x;
    }
}
int dep[N],siv[N],fa[N];
int Solve(int x){
    int cnt=r[x];
    siv[x]=1;
    for(auto p:e[x]){
        int y=p.first;
        if(siv[y]) continue ;
        fa[y]=x,dep[y]=dep[x]+1;
        int tmp=Solve(y);
        if(tmp==1){
            cnt^=1;
            ans[p.second]^=1;
        }
    }
    return cnt;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        
        tot=0;
        map<int,int> mp;
        for(int i=1;i<=n;i++){
            if(!mp[i-a[i]]) mp[i-a[i]]=++tot;
            u[i]=mp[i-a[i]];
            r[u[i]]^=1;
        }
        mp.clear();
        for(int i=1;i<=n;i++){
            if(!mp[i+a[i]]) mp[i+a[i]]=++tot;
            v[i]=mp[i+a[i]];
        }
        for(int i=1;i<=n;i++){
            e[u[i]].push_back({v[i],i});
            e[v[i]].push_back({u[i],i});
        }

        int err=0;
        for(int i=1,flag;i<=tot;i++){
            if(vis[i]) continue ;
            root=0,flag=1;
            DFS(i);
            if(!root) root=i,flag=0;
            int cnt=Solve(root);
            if(!cnt) continue ;
            if(!flag){
                err=1;
                continue ;
            }
            int pos=0;
            for(auto p:e[root]){
                int x=p.first;
                if(dep[x]&1) continue ;
                pos=x;
                ans[p.second]^=1;
                break ;
            }
            vector<int> pth;
            while(pos!=root){
                pth.push_back(pos);
                pos=fa[pos];
            }
            pth.push_back(root);
            reverse(allc(pth));
            for(int j=1;j<ssiz(pth);j++){
                for(auto p:e[pth[j]]){
                    if(p.first!=pth[j-1]) continue ;
                    ans[p.second]^=1;
                    break ;
                }
            }
        }

        if(err) cout<<"No"<<endl;
        else{
            cout<<"Yes"<<endl;
            for(int i=1;i<=n;i++){
                if(ans[i]) tmp[v[i]].push_back(i);
                else tmp[u[i]].push_back(i);
            }
            for(int i=1;i<=tot;i++){
                for(int j=0;j<ssiz(tmp[i]);j+=2) cout<<tmp[i][j]<<' '<<tmp[i][j+1]<<endl;
            }
        }

        for(int i=1;i<=tot;i++){
            e[i].clear(),tmp[i].clear();
            vis[i]=siv[i]=dep[i]=fa[i]=c[i]=r[i]=0;
        }
        for(int i=1;i<=n;i++){
            a[i]=u[i]=v[i]=ans[i]=0;
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 394ms
memory: 30572kb

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
21 32
39 42
43 45
46 47
49 56
57 58
62 63
64 65
66 68
70 71
73 74
75 77
80 81
82 87
88 95
97 101
102 103
105 106
116 117
118 137
148 155
156 158
160 164
166 167
169 171
172 176
177 182
183 184
190 191
192 193
200 208
209 210
228 229
237 238
239 241
242 243
245 247
251 252
253 254
255...

result:

ok 10 Cases (10 test cases)

Test #3:

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

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
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
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
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
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 493ms
memory: 40836kb

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: 781ms
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
4 6
7 8
13 23
47 57
62 63
84 107
114 122
208 210
271 274
307 417
481 489
495 507
536 548
565 659
791 1002
1122 1138
1147 1175
1256 1280
1324 1388
1414 1716
1973 2236
2386 2439
2616 2897
3257 3262
3375 3385
3412 3536
3674 3690
3779 4151
4371 4547
5149 5254
5337 5379
5575 5757
5900 5948
6377 6921
...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 246ms
memory: 20060kb

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
1 4
11 13
23 30
34 39
40 46
48 50
53 54
58 69
73 76
88 89
92 94
105 106
108 114
116 120
123 125
128 132
133 135
137 138
148 150
153 156
163 172
173 180
181 187
188 193
194 211
222 225
227 228
236 242
254 256
261 263
275 288
289 291
299 310
317 319
343 352
355 371
389 405
407 41...

result:

ok 1000 Cases (1000 test cases)