Codeforces Round #268 (Div. 2) D. Two Sets [stl

Codeforces Round #268 (Div. 2) D. Two Sets [stl - set + 暴力]

阅读量：6695 次

发布时间：2019-06-25

本文共 3826 字，大约阅读时间需要 12 分钟。

2014-10-10 06:12:37	GNU C++	Accepted	171 ms	7900 KB
2014-10-09 17:26:01	GNU C++	Wrong answer on test 9	30 ms	2700 KB
2014-10-09 17:20:58	GNU C++	Time limit exceeded on test 1	1000 ms	2700 KB
2014-10-09 17:16:09	GNU C++	Wrong answer on test 9	31 ms	2700 KB
2014-10-09 16:09:13	GNU C++	Wrong answer on test 6	15 ms	2700 KB

set真是太好用了，55555，要好好学stl

Little X has n distinct integers: p₁, p₂, ..., 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.

Input

The first line contains three space-separated integers n, a, b (1 ≤ n ≤ 10⁵; 1 ≤ a, b ≤ 10⁹). The next line contains n space-separated distinct integers p₁, p₂, ..., p_n (1 ≤ p_i ≤ 10⁹).

Output

If there is a way to divide the numbers into two sets, then print "YES" in the first line. Then print n integers: b₁, b₂, ..., 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).

Sample test(s)

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.

题解转自：

看到2Set我还真以为用2Set解，后来想想应该是2分匹配图，结果图左右两边分不出来，构不出图，弱爆了。。。唉。。早上起来又掉rating了

看了别人的解题报告，用的是直接暴力，能在a里处理的都放a集合，否则放入b集合，在b里开始遍历，如果b-x不在就去a里拿，如果a中也没有就输出NO，艾玛。。。。。

事实证明有时候想太多也不好

还能用并查集做，膜拜~~~

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
             9 #include
             
               10 #include
              
                11 //#include
               
                 12 13 #define N 100005 14 #define M 1000005 15 #define mod 1000000007 16 //#define p 10000007 17 #define mod2 100000000 18 #define ll long long 19 #define LL long long 20 #define maxi(a,b) (a)>(b)? (a) : (b) 21 #define mini(a,b) (a)<(b)? (a) : (b) 22 23 using namespace std; 24 25 int n,a,b; 26 map
                
                 mp; 27 set
                 
                  f,g; 28 vector
                  
                   c; 29 int x; 30 int res[N]; 31 int flag; 32 33 void ini() 34 { 35 memset(res,0,sizeof(res)); 36 flag=1; 37 mp.clear(); 38 f.clear(); 39 g.clear(); 40 c.clear(); 41 int i; 42 int y; 43 for(i=1;i<=n;i++){ 44 scanf("%d",&x); 45 mp[x]=i; 46 f.insert(x); 47 } 48 for(set
                   
                    ::iterator it=f.begin();it!=f.end();it++){ 49 y=*it; 50 if(f.find(a-y)==f.end()){ 51 c.push_back(y); 52 //c.push_back(a-y); 53 } 54 } 55 56 for(vector
                    
                     ::iterator it=c.begin();it!=c.end();it++){ 57 f.erase(*it); 58 g.insert(*it); 59 } 60 } 61 62 void solve() 63 { 64 while(g.empty()!=1){ 65 set
                     
                      ::iterator it=g.begin(); 66 int y=*it; 67 if(g.find(b-y)!=g.end()){ 68 res[ mp[y] ]=1; 69 res[ mp[b-y] ]=1; 70 g.erase(y);g.erase(b-y); 71 } 72 else{ 73 if(f.find(b-y)!=f.end()){ 74 res[ mp[y] ]=1; 75 res[ mp[b-y] ]=1; 76 g.erase(y); 77 f.erase(b-y); 78 if(f.find( a-(b-y) )!=f.end()){ 79 g.insert(a-(b-y)); 80 f.erase(a-(b-y)); 81 } 82 } 83 else{ 84 flag=0;return; 85 } 86 } 87 88 } 89 } 90 91 void out() 92 { 93 if(flag==0){ 94 printf("NO\n"); 95 } 96 else{ 97 printf("YES\n"); 98 printf("%d",res[1]); 99 for(int i=2;i<=n;i++){100 printf(" %d",res[i]);101 }102 printf("\n");103 }104 }105 106 int main()107 {108 // freopen("data.in","r",stdin);109 //freopen("data.out","w",stdout);110 // scanf("%d",&T);111 // for(int ccnt=1;ccnt<=T;ccnt++)112 // while(T--)113 while(scanf("%d%d%d",&n,&a,&b)!=EOF)114 {115 //if(n==0 && k==0 ) break;116 //printf("Case %d: ",ccnt);117 ini();118 solve();119 out();120 }121 122 return 0;123 }

转载于:https://www.cnblogs.com/njczy2010/p/4015173.html

你可能感兴趣的文章