B. Two Sets
Time Limit: 1 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/468/problem/B
Description
Little X has n distinct integers: p1, p2, ..., pn. He wants to divide all of them into two sets A and B. The following two conditions must be satisfied:
- If number x belongs to set A, then number a - x must also belong to set A.
- If number x belongs to set B, then number b - x must also belong to set B.
Help Little X divide the numbers into two sets or determine that it's impossible.
Input
The first line contains three space-separated integers n, a, b (1 ≤ n ≤ 105; 1 ≤ a, b ≤ 109). The next line contains n space-separated distinct integers p1, p2, ..., pn (1 ≤ pi ≤ 109).
Output
If there is a way to divide the numbers into two sets, then print "YES" in the first line. Then print n integers: b1, b2, ..., bn (bi equals either 0, or 1), describing the division. If bi equals to 0, then pi belongs to set A, otherwise it belongs to set B.
If it's impossible, print "NO" (without the quotes).
Sample Input
4 5 9
2 3 4 5
Sample Output
YES
0 0 1 1
HINT
题意
给你n个数，再给你俩集合，表示如果x在集合A里面的话，那么a-x也得在集合A
集合B同理
问你是否能够构造出来
题解：
直接暴力找就好了，如果能扔进A就扔进去，否则就扔B里面，就暴力
代码：
//qscqesze
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <bitset>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::ssecondnc_with_stdio(0);cin.tie(0)
#define maxn 100006
#define mod 1000000007
#define eps 1e-9
#define PI acos(-1)
const double EP = 1E- ;
int Num;
//const int inf=0first7fffffff;
const ll inf=;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//************************************************************************************* map<int,int> A,B;
queue<int> q;
vector<int>p; int main()
{
int n=read(),a=read(),b=read();
for(int i=;i<n;i++)
{
int x=read();p.push_back(x);
A[x]++;
}
for(int i=;i<n;i++)
{
if(A[p[i]]>&&A[a-p[i]]==)
q.push(p[i]);
}
while(!q.empty())
{
int now = q.front();
q.pop();
if(A[now]>&&A[a-now]==&&A[b-now]==)
{
cout<<"NO"<<endl;
return ;
}
--A[now];
--A[b-now];
++B[now];
++B[b-now];
if(A[b-now]==&&A[a-b+now]>)
q.push(a-b+now);
}
cout<<"YES"<<endl;
for(int i=;i<n;i++)
if(A[p[i]]>)
cout<<"0 ",--A[p[i]];
else
cout<<"1 ";
}