Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MAX 200010
- #define dbg(x) cout << #x << " = " << x << endl
- using namespace std;
- int n,a,b, ar[MAX], pos[MAX];;
- unordered_map <int, int> mp;
- class hopcroft_karp
- {
- public :
- vector <int> G[MAX];
- int n;
- int dis[MAX], Q[MAX], parent[MAX], L[MAX], R[MAX];
- void init(int _n)
- {
- n = _n;
- for(int i=0;i<=n;i++)G[i].clear();
- }
- void addEdge(int u,int v)
- {
- G[u].push_back(v);
- }
- bool dfs(int i)
- {
- int j = 0;
- int len = G[i].size();
- for (j = 0; j < len; j++)
- {
- int x = G[i][j];
- if (L[x] == -1 || (parent[L[x]] == i))
- {
- if (L[x] == -1 || dfs(L[x]))
- {
- L[x] = i;
- R[i] = x;
- return (true);
- }
- }
- }
- return false;
- }
- bool bfs()
- {
- int i, j, x, f = 0, l = 0;
- memset(dis, -1, sizeof(dis));
- for (i = 1; i <= n; i++)
- {
- if (R[i] == -1)
- {
- Q[l++] = i;
- dis[i] = 0;
- }
- }
- while (f < l)
- {
- i = Q[f++];
- int len = G[i].size();
- for (j = 0; j < len; j++)
- {
- x = G[i][j];
- if (L[x] == -1) return true;
- else if (dis[L[x]] == -1)
- {
- parent[L[x]] = i;
- dis[L[x]] = dis[i] + 1;
- Q[l++] = L[x];
- }
- }
- }
- return false;
- }
- int matchOf(int u)
- {
- return L[u];
- }
- int getMatch()
- {
- int i, j, counter = 0;
- memset(L, -1, sizeof(L));
- memset(R, -1, sizeof(R));
- while (bfs())
- {
- for (i = 1; i <= n; i++)
- {
- if (R[i] == -1 && dfs(i)) counter++;
- }
- }
- return counter;
- }
- };
- int main()
- {
- int i, j;
- while (scanf("%d %d %d", &n, &a, &b) != EOF)
- {
- hopcroft_karp hk;
- hk.init(n);
- mp.clear();
- for (i = 1; i <= n; i++)
- {
- scanf("%d", &ar[i]);
- mp[ar[i]] = i;
- }
- bool flag = true;
- for (i = 1; i <= n; i++)
- {
- int x = a - ar[i];
- int y = b - ar[i];
- int c = mp[x], d = mp[y];
- if (!c && !d)
- {
- flag = false;
- break;
- }
- if (c)
- {
- hk.addEdge(i,c);
- //G[i].push_back(c);
- }
- if (d) {
- hk.addEdge(i,d);// = G[i].push_back(d);
- }
- }
- if (!flag) puts("NO");
- else
- {
- int res = hk.getMatch();
- if (res == n)
- {
- puts("YES");
- for (i = 1; i <= n; i++)
- {
- int x = hk.matchOf(i);//L[i];
- if ((ar[i] + ar[x]) == a) pos[i] = 0;
- else pos[i] = 1;
- }
- for (i = 1; i <= n; i++) printf("%d ", pos[i]);
- puts("");
- }
- else puts("NO");
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment