Codeforces Round #268 (Div. 2) D Two Sets[并查集]

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <map>
using namespace std;

const int N = 1e5 + 5;
map<int, int> m;
int father[N], arr[N];

int find(int x)
{
    if(father[x] == x) return x;
    else return father[x] = find(father[x]);
}

void Union(int x, int y)
{
    int a = find(x), b = find(y);
    if(a == b) return ;
    father[a] = b;
}

int main()
{
//    freopen("1.txt", "r", stdin);
    int n, a, b;
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i ++){
        cin >> arr[i];
        m[arr[i]] = i;// 离散化一下就好。。
    }
    for(int i = 1; i <= n + 2; i ++){
        father[i] = i;
    }
    for(int i = 1; i <= n; i ++){
        if(m[a - arr[i]]){
            Union(i, m[a - arr[i]]);// if x and a - x exit, then them is a union.. but not must in A.
        }
        else Union(i, n + 2);// if x exit but a - x not exit, then x not in A. must in B.
        if(m[b - arr[i]]){// if x and b - x exit, then them is a union.. same above
           Union(i, m[b - arr[i]]);
        }
        else Union(i, n + 1);
    }
    if(find(n + 1) == find(n + 2)){
        cout << "NO" << endl;
    }
    else {
        cout << "YES" << endl;
        for(int i = 1; i <= n; i ++){
            if(i >= 2) printf(" ");
            if(find(i) ==  find(n + 1)){
                printf("0");
            }
            else printf("1");
        }
        printf("\n");
    }
    return 0;
}