468B

Description

We have $n$ ($1 \leq n \leq 10^5$) distinct integers $q_1~q_n$, $a$ and $b$. There are two sets $A$ and $B$. If $x$ belongs to $A$, $A$ must also contains $a-x$. It is the same with $B$ and $b$. Output how $q$s can be divided into the two sets. Each $q$ belongs and only belongs to one set.

Tutorial

If we have number $x$ and $a-x$, they should be in the same set. If $x$ belongs to $A$, it is obvious that $a-x$ belongs to $A$. If $x$ is not in $A$, then $a-x$ cannot find its partner in $A$, so they it cannot be in $A$ any more. Therefore, they can only all be in $B$. It is the same as the number x, b - x.

In additon, we should also know that if $a-x$ does not exist, $x$ can only belong to $B$. It is the same as $A$.

So we can use Disjoint Sets to solve this problem. Join the $q$s that must belongs to one set. Join those who must belong to $A$ with a special node. Join those who must belong to $B$ with another special node. Finally, if the two special nodes are in joined, there is no solution. Otherwise, solution exists.

Use STL map to get the positions of $a-x$ and $b-x$.

Solution

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

#define D(x) 
#define MAX_N 100005

int sum_a, sum_b;
int f[MAX_N];
int n;

struct Disjoint_sets
{
    int father[MAX_N];

    Disjoint_sets()
    {}

    Disjoint_sets(int n)
    {
        for (int i = 0; i < n; i++)
        {
            father[i] = i;
        }
    }

    int root(int a)
    {
        int ret = a;
        while (father[ret] != ret)
            ret = father[ret];
        while (father[a] != a)
        {
            int b = a;
            a = father[a];
            father[b] = ret;
        }
        return ret;
    }

    void join(int a, int b)
    {
        father[root(a)] = father[root(b)];
    }
}d_set;

void input()
{
    scanf("%d%d%d", &n, &sum_a, &sum_b);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &f[i]);
    }
}

bool work()
{
    d_set = Disjoint_sets(n + 2);
    map<int, int> pos;
    for (int i = 0; i < n; i++)
    {
        pos[f[i]] = i;
    }
    for (int i = 0; i < n; i++)
    {
        if (pos.find(sum_a - f[i]) != pos.end())
        {
            d_set.join(i, pos[sum_a - f[i]]);
        }else
        {
            d_set.join(i, n);
        }
        if (pos.find(sum_b - f[i]) != pos.end())
        {
            d_set.join(i, pos[sum_b - f[i]]);
        }else
        {
            d_set.join(i, n + 1);
        }
    }
    return d_set.root(n) != d_set.root(n + 1);
}

void output()
{
    puts("YES");
    for (int i = 0; i < n; i++)
    {
        if (i != 0)
        {
            putchar(' ');
        }
        if (d_set.root(i) == d_set.root(n))
        {
            putchar('1');
        }else
        {
            putchar('0');
        }
    }
}

int main()
{
    input();
    if (!work())
    {
        puts("NO");
    }else
    {
        output();
    }
    return 0;
}