QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#588288 | #5423. Perfect Matching | ship2077 | AC ✓ | 402ms | 32852kb | C++23 | 1.5kb | 2024-09-25 09:07:04 | 2024-09-25 09:07:05 |
Judging History
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;}
详细
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)