题意：有n个互不相同的整数： p1,p2,…,pn 。把这些整数分到两个集合A和B里边。但是要符合下面两个条件。

如果x属于A，那么a-x也肯定属于A。

如果x属于B，那么b-x也肯定属于B。

判断一下是否存在一种方案来分配这些数字到集合A，B中。

注意：如果一个集合为空也是可以的。

思路：思路是很简单的就是迷之WA…牛客上面的数据水得可以快排+二分都过了下标明明都不对…果然是用脚造的数据…然后用并查集做结果一直WA在第8组数据…可是找不出来哪儿错了…找题解结果都是千篇一律的代码 可怕难道你们的思路都一模一样的嘛qwq本弱找不出错哪儿了先放在这儿…

update：查出错误了 a-num[i]可以不等于b-num[i]啊 少考虑了一种a-num[i]存在而且b-num[i]存在的情况

对于一个x来说，能分成以下4种情况（这里a!=b）：

1.a-x不存在，b-x不存在。这种情况直接输出NO。

2.a-x存在，b-x不存在。这种情况把x和a-x放在集合A中。

3.a-x不存在，b-x存在。这种情况把x和b-x放在集合B中。

4.a-x存在，b-x存在。这种情况比较我们就不能直接确定要放A还是要放B了。

1⃣把x和a-x放入集合A，那么b-x肯定也要放入集合A，那么就说明存在y使得y=a-b+x。

2⃣把x和b-x放入集合B，那么a-x肯定也要放入集合B，那么就说明存在y使得y=b-a+x。

假设有y=a-b+x和y=b-a+x同时存在，则有a=b，矛盾。所以上面两种情况只可能存在一种或都不存在。如果都不存在，那么我们就无法决定把x和a-x和b-x放到集合A中还是集合B中，因为放到那一边都会剩下另一个无法去放，所以就输出NO。这里用并查集来维护即可。

代码：

WA代码：

int n;
int par[100010],high[100010],num[100010];
map<int,int>mp;
void init()
{
    for(int i=0;i<=n+1;i++)
    {
        par[i]=i;
        high[i]=0;
    }
}
int find(int x)
{
    if(par[x]==x)return x;
    return par[x]=find(par[x]);
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(high[x]<high[y])par[x]=y;
    else
    {
        par[y]=x;
        if(high[x]==high[y])high[x]++;
    }
}
bool same(int x,int y)
{
    return find(x)==find(y);
}
int main()
{
    int a,b,MAX=-1;
    scanf("%d%d%d",&n,&a,&b);
    for(int i=2;i<=n+1;i++)
    {
        scanf("%d",&num[i]);
        MAX=max(MAX,num[i]);
        mp[num[i]]=i;
    }
    if(MAX>=max(a,b)){printf("NO\n");return 0;}
    init();
    int flag=0;
    for(int i=2;i<=n+1&&flag==0;i++)
    {
        //printf("i=%d par[i]=%d find(i)=%d\n",i,par[i],find(i));            //printf("i=%d\n",i);
        int sign=0;
        if(mp[b-num[i]])
        {
            //printf("(%d)\n",par[1]);
            //printf("!\n");
            unite(1,i);
            unite(1,mp[b-num[i]]);
            sign++;
        }
        if(sign==0&&mp[a-num[i]])
        {
            //printf("?\n");
            unite(0,i);
            unite(0,mp[a-num[i]]);
            sign++;
        }
        if(sign==0)flag++;
    }
    if(flag!=0)printf("NO\n");
    else
    {
        printf("YES\n");
        for(int i=2;i<n+1;i++)
            printf("%d ",find(i));
        printf("%d\n",find(n+1));
    }
    return 0;
}

AC代码：

int n;
int par[100010],high[100010],num[100010];
map<int,int>mp;
void init()
{
    for(int i=0;i<=n+1;i++)
    {
        par[i]=i;
        high[i]=0;
    }
}
int find(int x)
{
    if(par[x]==x)return x;
    return par[x]=find(par[x]);
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(high[x]<high[y])par[x]=y;
    else
    {
        par[y]=x;
        if(high[x]==high[y])high[x]++;
    }
}
bool same(int x,int y)
{
    return find(x)==find(y);
}
int main()
{
    int a,b,MAX=-1;
    scanf("%d%d%d",&n,&a,&b);
    for(int i=2;i<=n+1;i++)
    {
        scanf("%d",&num[i]);
        MAX=max(MAX,num[i]);
        mp[num[i]]=i;
    }
    if(MAX>=max(a,b)){printf("NO\n");return 0;}
    init();
    for(int i=2;i<=n+1;i++)
    {
        if(mp[b-num[i]])unite(i,mp[b-num[i]]);
        else unite(i,0);
        if(mp[a-num[i]])unite(i,mp[a-num[i]]);
        else unite(i,1);//因为只能属于其中一类
    }
    if(find(0)==find(1))printf("NO\n");
    else
    {
        printf("YES\n");
        for(int i=2;i<=n+1;i++)
        {
            if(find(i)==find(0))printf("0");
            else printf("1");
            if(i!=n+1)printf(" ");
        }
        printf("\n");
    }
    return 0;
}