XOR Partition
Contest: Educational Codeforces Round 152 (Rated for Div. 2)
Difficulty rating: 2700
Tags: binary search, bitmasks, data structures, divide and conquer, greedy, trees

For a set of integers $$$S$$$, let's define its cost as the minimum value of $$$x \oplus y$$$ among all pairs of different integers from the set (here, $$$\oplus$$$ denotes bitwise XOR). If there are less than two elements in the set, its cost is equal to $$$2^{30}$$$.

You are given a set of integers $$$\{a_1, a_2, \dots, a_n\}$$$. You have to partition it into two sets $$$S_1$$$ and $$$S_2$$$ in such a way that every element of the given set belongs to exactly one of these two sets. The value of the partition is the minimum among the costs of $$$S_1$$$ and $$$S_2$$$.

Find the partition with the maximum possible value.

Input format:
The first line contains $$$n$$$ ($$$2 \le n \le 200000$$$) — the number of elements in the set.

The second line contains $$$n$$$ distinct integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — the elements of the set.

Output format:
Print a string $$$n$$$ characters 0 and/or 1 describing the partition as follows: the $$$i$$$-th character should be 0 if the element $$$a_i$$$ belongs to $$$S_1$$$, otherwise, that character should be 1.

If there are multiple optimal answers, print any of them.

Constraints:
Time limit: 7.0 s
Memory limit: 512.0 MB

Example input:
5
42 13 1337 37 152

Example output:
10001

Example input:
4
1 2 3 4

Example output:
1100

Editorial:
Disclaimer: the model solution to this problem is a bit more complicated than most of the solutions written by participants, but I will still use it for the editorial so that I can explain some of the classical techniques appearing in it.
Suppose we have built a graph on $$$n$$$ vertices, where each pair of vertices is connected by an edge, and the weight of the edge connecting $$$i$$$ with $$$j$$$ is $$$a_i \oplus a_j$$$. If we treat the partition of the set as a coloring of this graph, then the cost of the partition is equal to the minimum weight of an edge connecting two vertices of the same color. So, suppose we want to check that the answer is at least $$$x$$$. It means that every edge with weight less than $$$x$$$ should connect two vertices of different colors; so, the graph where we erase all edges with weight greater than or equal to $$$x$$$ should be bipartite. This allows us to write a binary search solution if we somehow understand how to construct the graph and check that it is bipartite implicitly, but this is not the way the model solution goes.
Instead, suppose we do the following greedy. Initially, let the graph be empty. Then, we add all edges with weight $$$1$$$, and check if it is bipartite. Then, we add all edges with weight $$$2$$$, and check if it is bipartite. And so on, until the graph is no longer bipartite.
Of course, there are $$$O(n^2)$$$ edges, so this is too slow. But in fact, we don't need all the edges for this graph. Some of the edges we added didn't really affect the coloring of the graph: if, in this process, we add an edge which connects two vertices from the same component, one of the following two things happens:
• if it connects two vertices of the same color, then the graph is no longer bipartite;
• otherwise, this edge actually does not change anything in the coloring.
Now, suppose we stop before making the graph non-bipartite. It means if an edge we added was connecting two vertices from the same component, that edge was actually redundant.
Let's take a look again at what we're actually doing. Initially, the graph is empty. Then, we consider all possible edges in ascending order of their weights; if an edge connects two vertices in different components, it should be added to the graph (and it affects the coloring), otherwise, it does not matter (unless it makes us stop the algorithm, since the graph is no longer bipartite). Doesn't it sound familiar? Yup, it is almost like Kruskal's algorithm.
And in fact, the problem can be solved as follows: build any MST of this graph, and use it to form the two-coloring (paint the vertices in such a way that every edge from MST connects two vertices of different colors). The paragraph below contains the formal proof that this coloring is optimal; feel free to skip it if you're not interested in the strict proof.
Formal proof: suppose that, if we color the vertices using the MST, we get an answer equal to $$$x$$$. This means that there are two vertices $$$i$$$ and $$$j$$$ such that their colors are the same, and $$$a_i \oplus a_j = x$$$. Let us consider the cycle formed by the edge from $$$i$$$ to $$$j$$$ and the path from $$$j$$$ to $$$i$$$ in the MST. Since these two vertices have the same colors, this cycle contains an odd number of edges — so, at least one edge on this cycle will connect vertices of the same color no matter how we paint the graph. And there are no edges on this cycle with weight greater than $$$x$$$ — otherwise, that edge would be replaced by the edge $$$(i,j)$$$ in the MST. So, at least one edge with weight $$$\le x$$$ will be connecting two vertices of the same color, and thus the answer cannot be greater than $$$x$$$.
Okay, now we have to actually build the MST in this graph. XOR-MST is a fairly classical problem (it was even used in one of the previous Educational Rounds several years ago). I know two different solutions to it: the one based on Boruvka's algorithm and the D&C + trie merging method. I will describe the former one.
The classical Boruvka's algorithm is one of the algorithms of finding a minimum spanning tree. It begins with a graph containing no edges, and performs several iterations until it becomes connected. On each iteration, the algorithm considers each component of the graph and adds the minimum edge connecting any vertex from this component with any vertex outside this component (these edges are added at the same time for all components of the graph, so be careful about creating a cycle or adding the same edge twice; different methods can be used to prevent this — in the model solution, I memorize the edges I want to add on each iteration, then use a DSU to actually check which ones should be added without causing a cycle to appear).
During each iteration of the algorithm, the number of components decreases to at least half of the original number, so the algorithm works in $$$O(I \log n)$$$, where $$$I$$$ is the complexity of one iteration. Usually, $$$I$$$ is $$$O(m)$$$ since we need to consider each edge of the graph twice; but in this problem, we can perform one iteration of Boruvka's algorithm much faster, in $$$O(n \log A)$$$, where $$$A$$$ is the constraint on the numbers in the input.
It can be done as follows: maintain a trie data structure which stores all values of $$$a_i$$$ and allows processing a query "given an integer $$$x$$$, find the value $$$y$$$ in the data structure such that $$$x \oplus y$$$ is the minimum possible" (this can be done with a trie descent). When we consider a component and try to find the minimum edge leading outside of it, we first delete all vertices belonging to this component from the data structure; then, for each vertex from the component, find the best vertex in the data structure; and then, insert all vertices back. That way, a component of size $$$V$$$ will be processed in $$$O(V \log A)$$$, and the total time for one iteration is $$$O(n \log A)$$$.
All of this results in a solution with complexity $$$O(n \log n \log A)$$$.