QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#771620#5423. Perfect Matchingchenlinxuan0226RE 0ms0kbC++142.6kb2024-11-22 14:39:262024-11-22 14:39:26

Judging History

你现在查看的是最新测评结果

  • [2024-11-22 14:39:26]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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";
    }
}

详细

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

output:


result: