QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#650312#5423. Perfect Matchingucup-team3161#AC ✓492ms81800kbC++171.3kb2024-10-18 14:34:122024-10-18 14:34:39

Judging History

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

  • [2024-10-18 14:34:39]
  • 评测
  • 测评结果:AC
  • 用时:492ms
  • 内存:81800kb
  • [2024-10-18 14:34:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
const int N=1e6+5;
int T,n,a[N],ds1[N],ds2[N],fa[N],z[N];
vector<pair<int,int>> e[N];vector<int> vc[N];
int find(int u) {return u==fa[u]?u:fa[u]=find(fa[u]);}
bool merge(int u,int v)
{u=find(u);v=find(v);if(u==v) return 0;fa[u]=v;return 1;}
void work(int ds[])
{sort(ds+1,ds+ds[0]+1);ds[0]=unique(ds+1,ds+ds[0]+1)-ds-1;}
int id(int ds[],int x) {return lower_bound(ds+1,ds+ds[0]+1,x)-ds;}
void dfs(int u,int f)
{
    for(auto [v,id]:e[u]) if(v!=f)
    {dfs(v,u);if(z[v]) z[v]^=1,vc[v].eb(id);else z[u]^=1,vc[u].eb(id);}
}
void slv()
{
    scanf("%d",&n);ds1[0]=ds2[0]=0;iota(fa+1,fa+n*2+1,1);fill(z+1,z+n*2+1,0);
    for(int i=1;i<=n*2;++i) e[i].clear(),vc[i].clear();
    for(int i=1;i<=n;++i)  
        scanf("%d",&a[i]),ds1[++ds1[0]]=a[i]+i,ds2[++ds2[0]]=a[i]-i;
    work(ds1);work(ds2);
    for(int i=1,u,v;i<=n;++i)
    {
        u=id(ds1,a[i]+i);v=n+id(ds2,a[i]-i);
        if(merge(u,v)) e[u].eb(v,i),e[v].eb(u,i);else z[u]^=1,vc[u].eb(i);
    }
    for(int i=1;i<=n*2;++i) if(find(i)==i) {dfs(i,0);if(z[i]) {puts("No");return;}}
    puts("Yes");
    for(int i=1,t;i<=n*2;++i)
    {t=0;for(auto j:vc[i]) {if(t) printf("%d %d\n",j,t),t=0;else t=j;}}
}
int main()
{
    scanf("%d",&T);
    while(T--) slv();return 0;
}

详细

Test #1:

score: 100
Accepted
time: 13ms
memory: 59712kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 254ms
memory: 71944kb

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
107 53
185 152
248 233
317 260
410 368
575 539
707 590
755 737
797 794
809 803
863 815
953 890
1055 1010
1064 1058
1082 1070
1139 1112
1175 1151
1247 1232
1382 1313
1520 1484
1610 1550
1715 1694
1748 1739
1781 1775
1868 1805
1949 1916
2006 1973
2078 2015
2168 2144
2306 2237
2327 2309
2375 2345
2...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 3ms
memory: 59552kb

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 240ms
memory: 81800kb

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
29330 29329
29332 29331
29334 29333
29336 29335
29338 29337
29340 29339
29342 29341
29344 29343
29346 29345
29348 29347
29350 29349
29352 29351
82228 82227
82230 82229
82232 82231
82234 82233
82236 82235
82238 82237
82240 82239
82242 82241
82244 82243
82246 82245
82248 82247
82250 82249
82252 82...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 492ms
memory: 72704kb

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
32 3
1932 170
3820 1986
5851 5658
7783 5902
8799 8281
9393 9282
10805 9892
13900 13027
17031 15615
20491 18370
22113 20817
31175 23424
32863 32797
37250 34960
38188 38102
39303 39104
45366 45082
56409 47987
59024 58265
62116 61232
65281 62789
71444 65387
76759 76524
78974 77522
80672 79799
82317...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 159ms
memory: 59076kb

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 15
22 23
33 34
37 36
47 48
57 59
66 67
72 73
74 75
77 78
98 99
107 108
112 113
127 128
131 130
142 144
147 148
151 152
155 156
161 162
165 167
170 171
179 180
183 185
184 186
192 193
198 199
200 202
205 207
210 211
212 213
214 215
220 221
232 233
243 245
260 261
262 263
266 ...

result:

ok 1000 Cases (1000 test cases)