QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#589115 | #5423. Perfect Matching | rotcar07 | AC ✓ | 507ms | 25900kb | C++20 | 1.1kb | 2024-09-25 16:14:04 | 2024-09-25 16:14:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int maxn=2e5+5;
int n;vector<pair<int,int>> e[maxn];
int dep[maxn],tmp[maxn];
vector<pair<int,int>> ans;
void dfs(int p,int f){
dep[p]=dep[f]+1;
int z=0;
for(auto [x,y]:e[p]){
if(!dep[x])dfs(x,p);
if(dep[x]>dep[p]){
if(tmp[x]) ans.emplace_back(tmp[x],y),tmp[x]=0;
else{
if(z) ans.emplace_back(z,y),z=0;
else z=y;
}
}
}
tmp[p]=z;
}
inline void solve(){
unordered_map<int,int> p[2];
int tot=0;
auto f=[&](int op,int x){if(!p[op].count(x))p[op][x]=++tot;return p[op][x];};
ans.clear();
cin>>n;
for(int i=1;i<=n;i++){
int x;cin>>x;
int a=f(0,x+i),b=f(1,x-i);
// cout<<a<<' '<<b<<'\n';
e[a].emplace_back(b,i),e[b].emplace_back(a,i);
}
for(int i=1;i<=tot;i++) if(!dep[i]) dfs(i,0);
if(ans.size()==n/2){
// cout<<"!!!";for(int i=1;i<=tot;i++) cout<<tmp[i]<<' ';cout<<'\n';
cout<<"Yes\n";
for(auto [x,y]:ans)cout<<x<<' '<<y<<'\n';
}
else cout<<"No\n";
for(int i=1;i<=tot;i++) e[i].clear(),dep[i]=tmp[i]=0;
}
int main(){
int t;cin>>t;
while(t--) solve();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3820kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 5 2 6 3 Yes 1 3 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 377ms
memory: 14300kb
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: 1ms
memory: 3528kb
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 2 3 4 5 6 7 8 1 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 36 37 38 35 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 39 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: 455ms
memory: 25900kb
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 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 10...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 507ms
memory: 16628kb
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 1600 1725 14495 23105 33602 36346 81132 92548 8961 29263 41302 83637 11086 16914 34736 778 12537 4360 99552 2005 97953 92893 58176 30631 70597 19622 37677 26691 27149 66364 67617 10211 17075 44140 57643 11472 23176 35741 95323 12598...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 219ms
memory: 4056kb
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 4 11 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...
result:
ok 1000 Cases (1000 test cases)