#P6995. [2017年成都七中集训]集合
[2017年成都七中集训]集合
集合
问题描述
小明非常喜欢数字。最近他的妈妈送给他了一个由 个非负整数构成的序列(按原下标区分相同数值)。小明非常喜欢和小刚玩。他立即决定把他 n 个数字中的一部分送给小刚。为了让游戏更加有趣,小明决定使得送出的数字集合满足如下条件:
我们用 表示小明的数字集合的 xor 值,用 x2 表示小刚的数字集合的 xor 值。要使得 尽可能地大。假如有多种划分集合的方法使得集合满足上述条件,小明就要让 尽可能地小。
请按上述规则划分集合。如果有多种合适的方法,就找出其中任意一种方法。请注意,小明将一部分数字给了小刚之后,他可能就没有任何剩余的数字了。反之亦然,小明也可以不给小刚任何数字。在这两种情况下,我们都假定空集的值为 0。
输入格式
从标准输入读入。
输入的第一行包含一个整数 n,表示小明的妈妈给了他多少个数字。
第二行包含个用空格隔开的数字,保证它们都是不超过10^18 的非负整数。
输出格式
向标准输出写出。
输出一行,包含 个用空格隔开的整数,如果第 i 个数是 1,则表示小明保留给出的第 i 个数字,如果第 i 个数是 2,则表示小明把给出的第 i 个数字给了小刚。
样例输入
8
1 1 2 2 3 3 4 4
样例输出
1 2 1 2 2 2 1 2
数据规模与约定
对于 30%的数据,保证; 对于 60%的数据,保证;
对于 100%的数据,保证。