== 划分 查询 sample 在那 des elong equal
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:
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).
Example
Input
- 4 5 92 3 4 5
Output
- YES0 0 1 1
Input
- 3 3 41 2 4
Output
- NO
Note
It's OK if all the numbers are in the same set, and the other one is empty.
注意到如果 x 存在于 A 果 a-x、b-x(如果存在)也必须存在在 A,如果 a-(b-x) 、b-(a-x) 存在也必须在 A…… 即所有数可以划分为若干个集合,每个集合中的元素必须同时属于 A 或 B。这可以通过并查集维护。如果某数 x,a-x,b-x 都不存在那么这个数无法放到 A、B 任何一个,直接输出 NO 即可。
接下来维护并查集的状态,采用状态压缩,用两位 2 进制数表示可否放到 A、B 集合中。对于每个数 x,如果 a-x 存在则其可以放在集合 A,如果 b-x 存在则其可以放在集合 B。对每个并查集取其集合内所有可行状态的交集。显然并查集之间是不再存在互相影响的。如果每个并查集可行状态非 0 就表明一定存在符合题意的分配方式,任取每个集合的任意可行分配即可。
- 1#include 2#include < string > 3#include 4#include 5#include 6#include 7#include 8#include < set > 9#include 10#include 11#include 12#include 13#define mp make_pair 14 //#define P make_pair
- 15#define MIN(a, b)(a > b ? b: a) 16 //#define MAX(a,b) (a>b?a:b)
- 17 typedef long long ll;
- 18 typedef unsigned long long ull;
- 19 const int MAX = 1e5 + 5;
- 20 const int MAX_V = 25;
- 21 const int INF = 2e9 + 5;
- 22 const double M = 4e18;
- 23 using namespace std;
- 24 const int MOD = 1e9 + 7;
- 25 typedef pairint > pii;
- 26 const double eps = 0.000000001;
- 27#define rank rankk 28 map < int,
- int > par; //父亲
- 29 map < int,
- int > rank; //树的高度
- 30 //初始化n个元素
- 31 map < int,
- bool > chu;
- 32 map < int,
- int > st;
- 33 int an[MAX];
- 34 void init(int n) 35 {
- 36
- for (int i = 1; i) 37 {
- 38 par[i] = i;
- 39 rank[i] = 0;
- 40
- }
- 41
- }
- 42 //查询树的根,期间加入了路径压缩
- 43 int find(int x) 44 {
- 45
- if (!par[x]) 46 {
- 47 rank[x] = 0;
- 48
- return par[x] = x;
- 49
- }
- 50
- if (par[x] == x) 51
- return x;
- 52
- else 53
- return par[x] = find(par[x]);
- 54
- }
- 55 //合并x和y所属的集合
- 56 void unite(int x, int y) 57 {
- 58 x = find(x);
- 59 y = find(y);
- 60
- if (x == y) 61
- return;
- 62
- if (rank[x] < rank[y]) 63 par[x] = y;
- 64
- else 65 {
- 66 par[y] = x;
- 67
- if (rank[x] == rank[y]) 68 rank[x]++;
- 69
- }
- 70
- }
- 71 //判断x和y是否属于同一个集合
- 72 bool same(int x, int y) 73 {
- 74
- return find(x) == find(y);
- 75
- }
- 76 int n,
- a,
- b;
- 77 int x[MAX];
- 78 int main() 79 {
- 80 scanf("%d%d%d", &n, &a, &b);
- 81
- for (int i = 1; i <= n; i++) 82 {
- 83 scanf("%d", &x[i]);
- 84 chu[x[i]] = true;
- 85
- }
- 86
- for (int i = 1; i <= n; i++) 87 st[x[i]] = 0;
- 88
- for (int i = 1; i <= n; i++) 89 {
- 90 bool sta = false;
- 91
- if (chu[a - x[i]]) 92 {
- 93 sta = true;
- 94 unite(x[i], a - x[i]);
- 95 st[x[i]] |= 1;
- 96
- }
- 97
- if (chu[b - x[i]]) 98 {
- 99 sta = true;
- 100 unite(x[i], b - x[i]);
- 101 st[x[i]] |= 2;
- 102
- }
- 103
- if (!sta) 104
- return 0 * printf("NO\n");
- 105
- }
- 106
- for (int i = 1; i <= n; i++) 107 {
- 108 st[find(x[i])] &= st[x[i]];
- 109
- }
- 110
- for (int i = 1; i <= n; i++) 111
- if (!st[x[i]]) 112
- return 0 * printf("NO\n");
- 113 printf("YES\n");
- 114
- for (int i = 1; i <= n; i++) 115 {
- 116
- if (st[find(x[i])] & 1) 117 printf("0 ");
- 118
- else 119 printf("1 ");
- 120
- }
- 121 printf("\n");
- 122
- return 0;
- 123
- }
(并查集 \ 状态压缩)CodeForces - 469D Two Sets
来源: http://www.bubuko.com/infodetail-2116346.html