QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#771828 | #5423. Perfect Matching | cyc001 | AC ✓ | 979ms | 31772kb | C++23 | 2.6kb | 2024-11-22 15:53:51 | 2024-11-22 15:53:52 |
Judging History
answer
#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
#define fcin cin
#define fcout cout
class tree{
private:
vector<vector<pair<int,int>>> gr;
vector<int> id;
vector<int> sum,siz,vis;
auto dfs(int u,int fr=-1)->void{
sum[u]=siz[u];vis[u]=true;
for(auto&[v,w]:gr[u]) if(!vis[v]){
dfs(v,u);sum[u]+=(sum[v]-1);
if(sum[v]&1) id[w]=u;
else id[w]=v;
}else if(v!=fr&&id[w]==-1){
--sum[u];id[w]=v;
}
}
public:
auto link(int u,int v,int w){
gr[u].emplace_back(v,w);
gr[v].emplace_back(u,w);
}
auto setsiz(vector<int> _siz){siz=_siz;}
auto check(){
cir(i,0,(int)(gr.size())) if(!vis[i]) dfs(i);
return id;
}
tree(int _n,int _m):gr(_n),id(_m,-1),sum(_n),siz(_n),vis(_n){}
};
class dsu{
private:
vector<int> f,siz;
public:
auto findset(int u)->int{
return f[u]==u?u:f[u]=findset(f[u]);
}
auto merge(int u,int v){
u=findset(u);v=findset(v);
if(u==v) return;
f[u]=v;siz[v]+=siz[u];
}
auto size(auto u){return siz[findset(u)];}
dsu(int _n):f(_n),siz(_n,1){iota(f.begin(),f.end(),0);}
};
int main(){
ios::sync_with_stdio(false),fcin.tie(nullptr);
int T;fcin>>T;
while(T--) []{
int n;fcin>>n;vector<int> a(n);
for(auto&i:a) fcin>>i;
map<int,vector<int>> ax,bx;
cir(i,0,n) ax[a[i]-i].push_back(i);
cir(i,0,n) bx[a[i]+i].push_back(i);
vector<vector<int>> fr(n);
dsu ds(n);
auto cccnt=-1;
vector<int> siz;
for(auto&[a,b]:ax){
++cccnt;
for(auto&i:b) fr[i].push_back(cccnt);
cir(i,1,(int)(b.size())) ds.merge(b[i-1],b[i]);
siz.push_back(b.size());
}
for(auto&[a,b]:bx){
++cccnt;
for(auto&i:b) fr[i].push_back(cccnt);
cir(i,1,(int)(b.size())) ds.merge(b[i-1],b[i]);
siz.push_back(b.size());
}
auto vaild=true;
cir(i,0,n) vaild&=(!(ds.size(i)&1));
if(!vaild) return fcout<<"No"<<'\n',void();
tree tr(cccnt+1,n);
cir(i,0,n) tr.link(fr[i][0],fr[i][1],i);
tr.setsiz(siz);
const auto id=tr.check();
map<int,vector<int>> idx;
cir(i,0,n) idx[id[i]].push_back(i);
fcout<<"Yes"<<'\n';
for(auto&[a,b]:idx){
for(auto i=0;i<(int)(b.size());i+=2) fcout<<b[i]+1<<' '<<b[i+1]+1<<'\n';
}
}();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 2 5 3 6 1 4 Yes 2 4 1 3 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 350ms
memory: 26536kb
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 140 142 34 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 2...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3860kb
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 35 36 37 38 1 2 3 4 5 6 7 8 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 69 70 71 72 73 74 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 344ms
memory: 31772kb
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 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 71778 71779 71780 71781 71782 71783 71784 71785 71786 71787 71788 71789 71790 71791 71792 71793 71794 71795 71796 71797 71798 71799 71800 71801 71...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 979ms
memory: 29672kb
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 99327 99702 97303 99263 98626 98946 95828 96046 95341 97927 97343 98426 97616 97711 95342 98589 93465 99602 93214 96560 93180 97318 92136 96630 94719 95270 94735 96521 93661 95654 92554 97683 92059 92301 97337 97522 90752 94744 91889 93560 93095 95731 91882 96890 97295 98433 90174 92734 95536 97...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 262ms
memory: 3868kb
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 2 8 10 15 19 44 52 59 60 63 67 78 80 84 95 97 99 100 115 117 131 140 144 162 167 168 185 186 189 196 197 199 202 206 207 209 215 216 217 218 233 234 238 239 245 247 248 253 258 264 265 272 280 281 286 290 305 308 314 316 321 322 327 330 334 353 360 362 369 372 379 380 385 388 4...
result:
ok 1000 Cases (1000 test cases)