302429: CF468B. Two Sets

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Two Sets

题意翻译

> 给出 $n$ 个各不相同的数字,将它们分别放入 $A$ 和 $B$ 两个集合中,使它们满足: > * 若数字 $x$ 在集合 $A$ 中,那么数字 $a-x$ 也在集合 $A$ 中; > * 若数字 $x$ 在集合 $B$ 中,那么数字 $b-x$ 也在集合 $B$ 中。 > **输入格式:** > > 输入的第一行输入三个整数 $n,a,b (1 \leq n \leq 10^{5} ; 1 \leq a,b \leq 10^{9} )$。 > > 输入的第二行有 $n$ 个各不相同的正整数,且每个正整数的数值大小都在 $[1,10^{9}]$ 内。 > **输出格式:** > > 若不能能将这 $n$ 个数在满足条件的情况下全部放入 $A$ 和 $B$ 这两个集合中,则输出 `NO` 。 > > 若这 $n$ 个数在满足条件的情况下能被全部放入 $A$ 和 $B$ 这两个集合中,则第一行输出 `YES` ,第二行输出 $n$ 个数 $0$ 或 $1$ ,第 $i$ 个数为 $0$ 表示第 $i$ 个数在集合 $A$ 中,第 $i$ 个数为 $1$ 表示第 $i$ 个数在集合 $B$ 中。

题目描述

Little X has $ n $ distinct integers: $ p_{1},p_{2},...,p_{n} $ . 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.

输入输出格式

输入格式


The first line contains three space-separated integers $ n,a,b $ $ (1<=n<=10^{5}; 1<=a,b<=10^{9}) $ . The next line contains $ n $ space-separated distinct integers $ p_{1},p_{2},...,p_{n} (1<=p_{i}<=10^{9}) $ .

输出格式


If there is a way to divide the numbers into two sets, then print "YES" in the first line. Then print $ n $ integers: $ b_{1},b_{2},...,b_{n} $ ( $ b_{i} $ equals either $ 0 $ , or $ 1 $ ), describing the division. If $ b_{i} $ equals to $ 0 $ , then $ p_{i} $ belongs to set $ A $ , otherwise it belongs to set $ B $ . If it's impossible, print "NO" (without the quotes).

输入输出样例

输入样例 #1

4 5 9
2 3 4 5

输出样例 #1

YES
0 0 1 1

输入样例 #2

3 3 4
1 2 4

输出样例 #2

NO

说明

It's OK if all the numbers are in the same set, and the other one is empty.

Input

题意翻译

> 给出 $n$ 个各不相同的数字,将它们分别放入 $A$ 和 $B$ 两个集合中,使它们满足: > * 若数字 $x$ 在集合 $A$ 中,那么数字 $a-x$ 也在集合 $A$ 中; > * 若数字 $x$ 在集合 $B$ 中,那么数字 $b-x$ 也在集合 $B$ 中。 > **输入格式:** > > 输入的第一行输入三个整数 $n,a,b (1 \leq n \leq 10^{5} ; 1 \leq a,b \leq 10^{9} )$。 > > 输入的第二行有 $n$ 个各不相同的正整数,且每个正整数的数值大小都在 $[1,10^{9}]$ 内。 > **输出格式:** > > 若不能能将这 $n$ 个数在满足条件的情况下全部放入 $A$ 和 $B$ 这两个集合中,则输出 `NO` 。 > > 若这 $n$ 个数在满足条件的情况下能被全部放入 $A$ 和 $B$ 这两个集合中,则第一行输出 `YES` ,第二行输出 $n$ 个数 $0$ 或 $1$ ,第 $i$ 个数为 $0$ 表示第 $i$ 个数在集合 $A$ 中,第 $i$ 个数为 $1$ 表示第 $i$ 个数在集合 $B$ 中。

加入题单

上一题 下一题 算法标签: