← 返回题目列表

Codeforces · 1849/F

F. 异或分区

中文机器翻译题面 查看原题

对于一组整数$$$S$$$,我们将其成本定义为该组中所有不同整数对中$$$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$$$, ..., $$$a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — 集合的元素。

输出

打印描述分区的字符串 $$$n$$$ 个字符 0 和/或 1,如下所示:如果元素 $$$a_i$$$ 属于 $$$S_1$$$,则第 $$$i$$$ 个字符应为 0,否则该字符应为 1。

如果有多个最佳答案,则打印其中任何一个。

示例

输入 #1

5
42 13 1337 37 152

输出 #1

10001

输入 #2

4
1 2 3 4

输出 #2

1100

输入 #3

2
1 2

输出 #3

10

输入#4

8
7 6 5 4 3 2 1 0

输出#4

10010110