Для множества целых чисел $$$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, описывающую разделение следующим образом: $$$i$$$-й символ строки должен быть 0, если $$$a_i$$$ принадлежит $$$S_1$$$, в противном случае этот символ должен быть 1.
Если существует несколько оптимальных ответов — выведите любой из них.
5
42 13 1337 37 152
10001
4
1 2 3 4
1100
2
1 2
10
8
7 6 5 4 3 2 1 0
10010110
Название |
---|