Codeforces ラウンド #268 (ディビジョン 1)-B。 2 つのセット_html/css_WEB-ITnose

B. 2 セット

テストごとの制限時間 1 秒

テストごとのメモリ制限 256 メガバイト

小さな X には n 個の異なる整数があります: p1、?p2、?。 ..、?pn.彼は、それらすべてを 2 つの集合 A と B に分割したいと考えています。次の 2 つの条件が満たされなければなりません:

数値 x が集合 A に属している場合、数値 a?-?x も集合 A に属している必要があります。 x が集合 B に属している場合、数値 b?-?x も集合 B に属している必要があります。

小さな X が数字を 2 つの集合に分けるか、それが不可能であると判断するのを手伝ってください。

入力

最初の行には 3 つのスペースが含まれています- で区切られた整数 n,?a,?b (1?≤?n?≤?105; 1?≤?a,?b?≤?109)。次の行には、スペースで区切られた n 個の個別の整数 p1,?p2,?...,?pn (1?≤?pi?≤?109) が含まれています。

出力

数値を除算する方法がある場合を 2 つのセットに分けて、最初の行に「YES」を出力します。次に、割り算を説明する n 個の整数: b1,?b2,?...,?bn (bi は 0 または 1 に等しい) を出力します。 bi が 0 に等しい場合、pi はセット A に属し、それ以外の場合はセット B に属します。

それが不可能な場合は、(引用符なしで) "NO" を出力します。

サンプルテスト

入力

4 5 92 3 4 5

出力

YES0 0 1 1

入力

3 3 41 2 4

出力

NO

注 ですすべての数字が同じセット内にあり、もう一方の数字が空であればOKです。

意解:この道题には非常に多くの解法があり、私はBFSを使用していますが、小さな蔙误失敗システムテキストのため、比赛因です。 我掴a - x 存在しない暂時間確定はb

集合、存存队列、その後BFS、但要注意一问题、但当前の数配对の数は集合里面の话、我们就要a集合里面的那

个数取到bset,如果没播取的,则出"NO",详细看代码吧!

AC代码:

#include <iostream>#include <cstdio>#include <queue>#include <map>using namespace std;const int M = 1e5 + 10;map<int,int>ms;queue<int>ls;int ma[M];int main(){    int n,a,b;    scanf("%d %d %d",&n,&a,&b);    for(int i = 0; i < n; i++)    {        scanf("%d", ma + i);        ms[ma[i]] = 1;    }    for(int i = 0; i < n; i++)        if(!ms[a - ma[i]]) ls.push(ma[i]);    while(!ls.empty())    {        int u = ls.front(),tp;        ls.pop();        if(ms[u] > 0 && ms[a - u] == 0 && ms[b - u] == 0)        {            puts("NO");            return 0;        }        --ms[u]; //表示已被取到b集合去了;        --ms[b - u];        tp = a - b + u;        if(ms[tp]) ls.push(tp);  //如果我所取的那个数是a集合里的,在bfs把另一个数取出来.    }    puts("YES");    for(int i = 0; i < n; i++)        if(ms[ma[i]] == 1) printf("0 ");        else printf("1 ");    puts("");    return 0;}