QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#208992 | #5423. Perfect Matching | ucup-team870 | AC ✓ | 314ms | 27932kb | C++17 | 1.5kb | 2023-10-09 23:38:25 | 2023-10-09 23:38:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define P pair<int,int>
#define ll long long
#define vi vector<int>
const int N=2e5+5;
P ans[N]; int top=0;
vector<P>tu[N];
unordered_map<int,int>mp1,mp2;
int dep[N];
int dfs(int now,int pre){
dep[now]=dep[pre]+1;
vi q;
for(auto [son,id]:tu[now]){
if(son==pre)continue;
if(dep[son]){
if(dep[son]>dep[now])q.push_back(id);
continue;
}
int res=dfs(son,now);
if(res)ans[++top]={id,res};
else q.push_back(id);
}
int res=0;
if(q.size()&1)res=q.back(),q.pop_back();
for(int i=0;i<q.size();i+=2){
ans[++top]={q[i],q[i+1]};
}
return res;
}
void slv(){
mp1.clear(); mp2.clear();
int n;cin>>n;
vi a(n+1);
rep(i,1,n){
cin>>a[i]; mp1[a[i]-i]=1; mp2[a[i]+i]=1;
}
int cnt=0;
for(auto &[_,v]:mp1)v=++cnt;
for(auto &[_,v]:mp2)v=++cnt;
rep(i,1,cnt)tu[i].clear(),dep[i]=0;
rep(i,1,n){
int u=mp1[a[i]-i],v=mp2[a[i]+i];
tu[u].push_back({v,i}); tu[v].push_back({u,i});
}
top=0;
rep(i,1,cnt){
if(dep[i])continue;
if(dfs(i,0)){
cout<<"No\n";return;
}
}
cout<<"Yes\n";
rep(i,1,top)cout<<ans[i].first<<' '<<ans[i].second<<'\n';
}
signed main(){
IOS
int T;cin>>T;
while(T--)slv();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9732kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 3 6 4 1 2 5 Yes 3 1 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 191ms
memory: 24500kb
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 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 2353 2419 24...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 2ms
memory: 8892kb
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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 100 99 29 30 31 32 34 33 35 36 37 38 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 28 27 69 70 71 72 74 73 1 2 3 4 5 6 7 8 59 60 61 62 64 65 66 67 63 68 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 167ms
memory: 27932kb
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 99931 99932 99933 99934 99935 99936 99937 99938 99939 99940 99941 99942 99943 99944 99945 99946 99947 99948 99949 99950 99951 99952 99953 99954 99955 99956 99957 99958 99959 99960 99961 99962 99963 99964 99965 99966 99967 99968 99969 99970 99971 99972 99973 99974 99975 99976 99977 99978 99979 99...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 314ms
memory: 21840kb
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 28 89504 8564 26518 1121 63463 129 36817 8931 95315 61541 96991 70110 81303 13611 16772 778 34736 55231 92637 3408 19162 59542 87006 416 97729 81132 92548 41302 83637 28333 92168 3610 71221 80993 88310 11544 74032 33052 80608 14756 42619 1661 3199 3633 47380 26691 37677 27149 66364 10211 67617 1...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 145ms
memory: 8452kb
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 3 5 26 28 29 36 38 41 43 45 49 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 370 3...
result:
ok 1000 Cases (1000 test cases)