QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#99961 | #5423. Perfect Matching | 1kri | AC ✓ | 1617ms | 46600kb | C++14 | 1.4kb | 2023-04-24 08:54:38 | 2023-04-24 08:54:40 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
int t,n,a[200005];
int tot1,tot2;
map<int,int> id1,id2;
vector<int> e[400005],e_id[400005];
int depth[400005];
int ans[200005][2],tot;
void add(int x,int y){
++tot;
ans[tot][0]=x,ans[tot][1]=y;
return;
}
int dfs(int now,int fa,int d){
depth[now]=d;
int qwq=-1;
for (int i=0;i<(int)e[now].size();i++){
int v=e[now][i],w=e_id[now][i];
if (v==fa)continue;
if (depth[v]==0){
int t=dfs(v,now,d+1);
if (t!=-1)add(t,w);
else if (qwq!=-1)add(qwq,w),qwq=-1;
else qwq=w;
}
else if (depth[v]<depth[now]){
if (qwq!=-1)add(qwq,w),qwq=-1;
else qwq=w;
}
}
return qwq;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
tot1=tot2=0;
id1.clear(),id2.clear();
for (int i=1;i<=2*n;i++){
e[i].clear();
e_id[i].clear();
depth[i]=0;
}
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
if (id1[a[i]-i]==0)id1[a[i]-i]=++tot1;
if (id2[a[i]+i]==0)id2[a[i]+i]=++tot2;
int x=id1[a[i]-i],y=id2[a[i]+i]+n;
e[x].push_back(y);
e_id[x].push_back(i);
e[y].push_back(x);
e_id[y].push_back(i);
}
tot=0;
for (int i=1;i<=2*n;i++)
if (depth[i]==0)dfs(i,0,1);
if (tot==n/2){
printf("Yes\n");
for (int i=1;i<=tot;i++)printf("%d %d\n",ans[i][0],ans[i][1]);
}
else printf("No\n");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 7ms
memory: 22556kb
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: 597ms
memory: 33308kb
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 21 22 77 78 3 79 137 138 200 201 139 202 242 244 287 289 308 309 314 315 310 316 320 321 335 337 380 382 395 396 322 397 449 450 458 459 451 460 461 462 479 480 463 481 515 517 518 520 524 526 554 556 566 567 617 619 659 660 568 661 734 736 761 763 788 790 851 853 902 903 932 933 904 934 977 978...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 2ms
memory: 22364kb
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: 666ms
memory: 46600kb
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: 1617ms
memory: 36820kb
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 13 14 89504 28 49 54 57 58 8564 26518 63463 1121 153 222 36811 36817 84 129 8931 95315 506 7625 536 1600 96991 61541 47 48 99 152 70110 81303 13611 16772 126 132 34736 778 62 7528 859 1003 92 127 513 768 66 118 288 2392 317 332 3113 3777 203 204 888 3225 56 59 427 479 188 559 88 100 5757 5965 82...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 227ms
memory: 22512kb
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 6 9 16 17 18 21 23 22 25 27 31 32 34 33 35 42 48 47 51 62 73 72 64 79 82 86 90 96 101 103 108 107 109 111 128 127 121 145 148 147 156 155 157 159 164 166 169 174 180 179 176 191 193 192 195 201 211 210 204 223 229 230 237 244 246 252 261 260 263 262 269 276 282 292 293 294 ...
result:
ok 1000 Cases (1000 test cases)