Two Sets

Pista 1

Podemos modelar los dos conjuntos como un grafo, con $p_i$ y $a - p_i$ conectados en el grafo $A$ , y $p_i$ conectado a $b - p_i$ en el grafo B.

Pista 2

¿Cómo puede haber una contradicción en las componentes conexas?

Explicación

Podemos tratar cada conjunto como un grafo con varias componentes conexas. Para cada $p_i$ , si $a - p_i$ existe, entonces $p_i$ y $a - p_i$ están en la misma componente conexa dentro del grafo $A$ , y de forma similar para $B$ . Cada número de la componente conexa debe pertenecer a un conjunto. Por lo tanto, nuestra contradicción viene de si hay un número $x$ en la componente tal que solo existe $a - x$ , y otro $y$ en la componente tal que solo existe $b - y$ , o viceversa.

Podemos comprobar cada componente por la contradicción usando DSU. El estado de la componente entera será la intersección de en qué grafo puede residir cada número de la componente.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++


#include <bits/stdc++.h>
using namespace std;
 
 
// BeginCodeSnip{DSU (from the module)}
class DSU {
  private:
	vector<int> parents;
	vector<int> sizes;
 
  public:
	DSU(int size) : parents(size), sizes(size, 1) {
		for (int i = 0; i < size; i++) { parents[i] = i; }
	}
 
	int get(int x) { return parents[x] == x ? x : (parents[x] = get(parents[x])); }
 
	bool unite(int x, int y) {
		int x_root = find(x);
		int y_root = find(y);
		if (x_root == y_root) { return false; }
 
		if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
		sizes[x_root] += sizes[y_root];
		parents[y_root] = x_root;
		return true;
	}
};
// EndCodeSnip
 
int main() {
	int n, a, b;
	cin >> n >> a >> b;
	vector<int> p(n);
	for (int i = 0; i < n; i++) { cin >> p[i]; }
 
	map<int, int> at;
	for (int i = 0; i < n; i++) { at[p[i]] = i; }
 
	DSU dsu(n);
	vector<int> can_A(n), can_B(n);
	for (int i = 0; i < n; i++) {
		if (at.count(a - p[i])) {
			can_A[i] = true;
			dsu.unite(i, at[a - p[i]]);
		}
		if (at.count(b - p[i])) {
			can_B[i] = true;
			dsu.unite(i, at[b - p[i]]);
		}
	}
 
	/*
	 * first bit activated if all numbers in component i can reside in
	 * graph A, and similarly the second bit for graph B
	 */
	vector<int> can_component(n, 3);
	for (int i = 0; i < n; i++) {
		int mask = 0;
		if (can_A[i]) mask += 1;
		if (can_B[i]) mask += 2;
		can_component[dsu.get(i)] &= mask;
	}
 
	for (int i = 0; i < n; i++) {
		if (!can_component[i]) {
			cout << "NO" << endl;
			return 0;
		}
	}
 
	cout << "YES" << endl;
	for (int i = 0; i < n; i++) {
		int comp_mask = can_component[dsu.get(i)];
		if (comp_mask == 1) {
			// only can be in set A
			cout << 0 << " ";
		} else {
			// can be in either set A or B
			cout << 1 << " ";
		}
	}
	cout << endl;
}