首页 > 代码库 > （并查集\状态压缩）CodeForces - 469D Two Sets

（并查集\状态压缩）CodeForces - 469D Two Sets

2024-10-05 00:45:02   217人阅读

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).

Example

Input
4 5 9
2 3 4 5
Output
YES
0 0 1 1
Input
3 3 4
1 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 <iostream>
  2 #include <string>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <queue>
  8 #include <set>
  9 #include <map>
 10 #include <list>
 11 #include <vector>
 12 #include <stack>
 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 pair<ll,int> 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<n;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


联系
我们