najimCseJu

Untitled

Dec 14th, 2017
244
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.38 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MAX 200010
  3. #define dbg(x) cout << #x << " = " << x << endl
  4.  
  5. using namespace std;
  6. int n,a,b, ar[MAX], pos[MAX];;
  7. unordered_map <int, int> mp;
  8. class hopcroft_karp
  9. {
  10. public :
  11.     vector <int> G[MAX];
  12.     int n;
  13.     int dis[MAX], Q[MAX], parent[MAX], L[MAX], R[MAX];
  14.     void init(int _n)
  15.     {
  16.         n = _n;
  17.         for(int i=0;i<=n;i++)G[i].clear();
  18.     }
  19.     void addEdge(int u,int v)
  20.     {
  21.         G[u].push_back(v);
  22.     }
  23.     bool dfs(int i)
  24.     {
  25.         int j = 0;
  26.         int len = G[i].size();
  27.         for (j = 0; j < len; j++)
  28.         {
  29.             int x = G[i][j];
  30.             if (L[x] == -1 || (parent[L[x]] == i))
  31.             {
  32.                 if (L[x] == -1 || dfs(L[x]))
  33.                 {
  34.                     L[x] = i;
  35.                     R[i] = x;
  36.                     return (true);
  37.                 }
  38.             }
  39.         }
  40.         return false;
  41.     }
  42.  
  43.     bool bfs()
  44.     {
  45.         int i, j, x, f = 0, l = 0;
  46.         memset(dis, -1, sizeof(dis));
  47.  
  48.         for (i = 1; i <= n; i++)
  49.         {
  50.             if (R[i] == -1)
  51.             {
  52.                 Q[l++] = i;
  53.                 dis[i] = 0;
  54.             }
  55.         }
  56.  
  57.         while (f < l)
  58.         {
  59.             i = Q[f++];
  60.             int len = G[i].size();
  61.             for (j = 0; j < len; j++)
  62.             {
  63.                 x = G[i][j];
  64.                 if (L[x] == -1) return true;
  65.                 else if (dis[L[x]] == -1)
  66.                 {
  67.                     parent[L[x]] = i;
  68.                     dis[L[x]] = dis[i] + 1;
  69.                     Q[l++] = L[x];
  70.                 }
  71.             }
  72.         }
  73.         return false;
  74.     }
  75.     int matchOf(int u)
  76.     {
  77.         return L[u];
  78.     }
  79.  
  80.     int getMatch()
  81.     {
  82.         int i, j, counter = 0;
  83.         memset(L, -1, sizeof(L));
  84.         memset(R, -1, sizeof(R));
  85.  
  86.         while (bfs())
  87.         {
  88.             for (i = 1; i <= n; i++)
  89.             {
  90.                 if (R[i] == -1 && dfs(i)) counter++;
  91.             }
  92.         }
  93.         return counter;
  94.     }
  95. };
  96.  
  97.  
  98. int main()
  99. {
  100.     int i, j;
  101.  
  102.     while (scanf("%d %d %d", &n, &a, &b) != EOF)
  103.     {
  104.         hopcroft_karp hk;
  105.         hk.init(n);
  106.         mp.clear();
  107.         for (i = 1; i <= n; i++)
  108.         {
  109.             scanf("%d", &ar[i]);
  110.             mp[ar[i]] = i;
  111.         }
  112.  
  113.         bool flag = true;
  114.         for (i = 1; i <= n; i++)
  115.         {
  116.             int x = a - ar[i];
  117.             int y = b - ar[i];
  118.  
  119.             int c = mp[x], d = mp[y];
  120.             if (!c && !d)
  121.             {
  122.                 flag = false;
  123.                 break;
  124.             }
  125.             if (c)
  126.             {
  127.                 hk.addEdge(i,c);
  128.                 //G[i].push_back(c);
  129.             }
  130.             if (d) {
  131.                 hk.addEdge(i,d);// = G[i].push_back(d);
  132.             }
  133.         }
  134.  
  135.         if (!flag) puts("NO");
  136.         else
  137.         {
  138.             int res = hk.getMatch();
  139.             if (res == n)
  140.             {
  141.                 puts("YES");
  142.                 for (i = 1; i <= n; i++)
  143.                 {
  144.                     int x = hk.matchOf(i);//L[i];
  145.                     if ((ar[i] + ar[x]) == a) pos[i] = 0;
  146.                     else pos[i] = 1;
  147.                 }
  148.  
  149.                 for (i = 1; i <= n; i++) printf("%d ", pos[i]);
  150.                 puts("");
  151.             }
  152.             else puts("NO");
  153.         }
  154.     }
  155.     return 0;
  156. }
Advertisement
Add Comment
Please, Sign In to add comment