QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#771628 | #5423. Perfect Matching | chenlinxuan0226 | TL | 2ms | 9776kb | C++14 | 2.5kb | 2024-11-22 14:41:55 | 2024-11-22 14:41:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int T,n,a[100001],fa[100001],siz[100001],cnte,w[100001],v[100001],com[100001];
map<int,vector<int>>s1,s2;
vector<int>Map[100001];
struct edge
{
int u,v,c;
}e[400001];
int find(int i)
{return fa[i]=(i==fa[i])?i:find(fa[i]);}
void clear()
{
for(int i=1;i<=n;i++)v[i]=0,com[i]=0;
}
void bfs(int s,int t)
{
vector<int>q(0);
q.push_back(s);
v[s]=1;
int h=0;
while(h<q.size())
{
int u=q[h++];
for(int&e_:Map[u])
{
auto&[x,y,c]=e[e_];
if(v[y])continue;
v[y]=1,com[y]=e_;
if(y==t)
{
int now=y;
while(now!=s)
e[com[now]].c^=1,e[com[now]^1].c^=1,now=e[com[now]].u;
return;
}
q.push_back(y);
}
}
}
void merge(int x,int y)
{
++cnte;
e[cnte<<1]={x,y,0};
e[cnte<<1|1]={y,x,0};
Map[x].push_back(cnte<<1);
Map[y].push_back(cnte<<1|1);
if(find(x)==find(y))return;
if((siz[fa[x]]&1)&&(siz[fa[y]]&1))clear(),bfs(w[fa[x]],w[fa[y]]),w[fa[y]]=w[fa[x]]=0;
w[fa[y]]=w[fa[x]]|w[fa[y]];
w[fa[x]]=0;
siz[fa[y]]+=siz[fa[x]],
siz[fa[x]]=0,
fa[fa[x]]=fa[y];
}
void onlymerge(int x,int y)
{
if(find(x)==find(y))return;
siz[fa[y]]+=siz[fa[x]],
siz[fa[x]]=0,
fa[fa[x]]=fa[y];
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>T;
while(T--)
{
cin>>n;
cnte=0;
s1.clear();
s2.clear();
for(int i=1;i<=n;i++)
cin>>a[i],s1[a[i]-i].push_back(i),fa[i]=i,siz[i]=1,Map[i].clear(),w[i]=i;
for(int i=1;i<=n;i++)
s2[a[i]-(n-i+1)].push_back(i);
for(auto&[x,y]:s1)
for(int i=1;i<y.size();i++)
onlymerge(y[i-1],y[i]);
for(auto&[x,y]:s2)
for(int i=1;i<y.size();i++)
onlymerge(y[i-1],y[i]);
int o=1;
for(int i=1;i<=n;i++)
o&=!(siz[i]&1);
if(!o)
{
cout<<"No\n";
continue;
}
for(int i=1;i<=n;i++)
fa[i]=i,siz[i]=1;
for(auto&[x,y]:s1)
for(int i=1;i<y.size();i++)
merge(y[i-1],y[i]);
for(auto&[x,y]:s2)
for(int i=1;i<y.size();i++)
merge(y[i-1],y[i]);
cout<<"Yes\n";
for(int i=1;i<=cnte;i++)
if(e[i<<1].c)cout<<e[i<<1].u<<" "<<e[i<<1].v<<"\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 9776kb
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: -100
Time Limit Exceeded
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 99986 99988 99974 99976 99968 99970 99965 99966 99962 99963 99959 99960 99957 99958 99954 99955 99947 99949 99945 99946 99933 99934 99921 99922 99917 99919 99915 99916 99912 99913 99902 99904 99897 99898 99882 99883 99878 99880 99875 99876 99854 99855 99836 99837 99833 99835 99825 99826 99819 99...