CF1849F XOR Partition

对于一个整数集合 $S$，我们定义它的代价为集合中所有不同整数对 $x, y$ 的 $x \oplus y$（这里 $\oplus$ 表示按位异或）中的最小值。如果集合中元素少于两个，则其代价为 $2^{30}$。 给定一个整数集合 $\{a_1, a_2, \dots, a_n\}$，你需要将其划分为两个集合 $S_1$ 和 $S_2$，使得每个元素恰好属于其中一个集合。划分的价值定义为 $S_1$ 和 $S_2$ 的代价中的较小值。 请你找到一种划分方式，使得划分的价值最大。

第一行包含一个整数 $n$（$2 \le n \le 200000$），表示集合中元素的个数。 第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < 2^{30}$），表示集合中的元素。

输出一个长度为 $n$ 的仅由 $0$ 和 $1$ 组成的字符串，描述集合的划分方式：如果第 $i$ 个元素 $a_i$ 属于 $S_1$，则第 $i$ 个字符为 $0$，否则为 $1$。 如果有多种最优方案，输出其中任意一种即可。

由 ChatGPT 4.1 翻译