Explanation

We can treat each set as a graph with several connected components. For each $p_i$, if $a - p_i$ exists, then $p_i$ and $a - p_i$ are in the same connected component inside graph $A$, and similarly for $B$. Each number in the connected component must belong to one set. Therefore, our condradiction comes from if there is a number $x$ in the component such that only $a - x$ exists, and another $y$ in the component such that only $b - y$ exists, or vice cersa.

We can check each component for the contradiction using DSU. The status of the whole component will be the intersection of what graph each number in the component can reside in.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

 Code Snippet: DSU (from the module) (Click to expand)

int main() {
	int n, a, b;
	cin >> n >> a >> b;
	vector<int> p(n);
	for (int i = 0; i < n; i++) { cin >> p[i]; }