QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#771620 | #5423. Perfect Matching | chenlinxuan0226 | RE | 0ms | 0kb | C++14 | 2.6kb | 2024-11-22 14:39:26 | 2024-11-22 14:39:26 |
answer
#include<bits/stdc++.h>
using namespace std;
int T,n,a[100001],fa[100001],siz[100001],cnte,w[100001],v[100001],com[100001],q[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)
{
int ta=0;
q[ta++]=s;
v[s]=1;
int h=0;
while(h<ta)
{
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[ta++]=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()
{
freopen("matching.in","r",stdin);
freopen("matching.out","w",stdout);
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";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7