#P6995. [2017年成都七中集训]集合

    ID: 6826 传统题 1000ms 256MiB 尝试: 5 已通过: 2 难度: 7 上传者: 标签>难度分类提高+/省选-线性代数与代数线性基异或消元位运算按位贪心CF2300

[2017年成都七中集训]集合

集合

问题描述

小明非常喜欢数字。最近他的妈妈送给他了一个由 nn 个非负整数构成的序列(按原下标区分相同数值)。小明非常喜欢和小刚玩。他立即决定把他 n 个数字中的一部分送给小刚。为了让游戏更加有趣,小明决定使得送出的数字集合满足如下条件:

我们用x1x1 表示小明的数字集合的 xor 值,用 x2 表示小刚的数字集合的 xor 值。要使得x1+x2x1+x2 尽可能地大。假如有多种划分集合的方法使得集合满足上述条件,小明就要让x1x1 尽可能地小。

请按上述规则划分集合。如果有多种合适的方法,就找出其中任意一种方法。请注意,小明将一部分数字给了小刚之后,他可能就没有任何剩余的数字了。反之亦然,小明也可以不给小刚任何数字。在这两种情况下,我们都假定空集的xorxor值为 0。

输入格式

从标准输入读入。

输入的第一行包含一个整数 n,表示小明的妈妈给了他多少个数字。

第二行包含nn个用空格隔开的数字,保证它们都是不超过10^18 的非负整数。

输出格式

向标准输出写出。

输出一行,包含nn 个用空格隔开的整数,如果第 i 个数是 1,则表示小明保留给出的第 i 个数字,如果第 i 个数是 2,则表示小明把给出的第 i 个数字给了小刚。

样例输入

8
1 1 2 2 3 3 4 4

样例输出

1 2 1 2 2 2 1 2

数据规模与约定

对于 30%的数据,保证n<=10n<=10; 对于 60%的数据,保证n<=1000n<=1000;

对于 100%的数据,保证n<=100000n<=100000。