QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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";
}
}
Details
Tip: Click on the bar to expand more detailed information
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...