QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#771623#5423. Perfect Matchingchenlinxuan0226TL 2ms9808kbC++142.5kb2024-11-22 14:40:052024-11-22 14:40:07

Judging History

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

  • [2024-11-22 14:40:07]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:9808kb
  • [2024-11-22 14:40:05]
  • 提交

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()
{
    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: 9808kb

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...

result: