← 返回题目列表

Codeforces · 1725/H

H. 热黑热白

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

有一天,你被接纳为 Chanek 博士的助手。查内克博士交给你的第一个任务就是保管和储存他的魔法宝石。

Chanek博士拥有$$$N$$$魔法石,其中$$$N$$$为偶数。这些魔法石的编号从 $$$1$$$ 到 $$$N$$$。魔法石$$$i$$$的强度为$$$A_i$$$。魔法石可以涂上两种颜色,即黑色或白色。你的任务是将魔法石涂成黑色或白色,并将魔法石存放到魔法系数为$$$Z$$$($$$0 \leq Z \leq 2$$$)的魔法盒中。魔法石的绘制必须以这样的方式完成:$$$\frac{N}{2}$$$黑色魔法石和$$$\frac{N}{2}$$$白色魔法石。

为两个整数 $$$x$$$ 和 $$$y$$$ 定义 $$$\text{concat}(x, y)$$$ 作为将 $$$x$$$ 的数字以十进制表示形式连接到 $$$y$$$ 左侧而不改变顺序的结果。例如,$$$\text{concat}(10, 24)$$$ 将得到 $$$1024$$$。

对于魔法系数为 $$$Z$$$ 的魔法盒,如果魔法石 $$$i$$$ 的颜色不同且 $$$\text{concat}(A_i, A_j) \times \text{concat}(A_j, A_i) + A_i \times A_j \equiv Z \mod 3$$$,则魔法石 $$$i$$$ 会与魔法石 $$$j$$$ 发生反应。正在发生反应的魔法石会非常热且危险。因此,你必须给魔法石上色,并以没有魔法石反应的方式确定魔法盒的魔法系数$$$Z$$$,或者报告如果不可能的话。

输入

第一行包含一个偶数 $$$N$$$ ($$$2 \le N \le 10^5$$$) — Chanek 博士拥有的魔法宝石数量。

第二行包含 $$$N$$$ 整数 $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \leq A_i \leq 10^9$$$) — 所有魔法石的强度。

输出

如果无法满足问题的条件,则输出$$$-1$$$。

否则,输出两行。第一行包含一个整数 $$$Z$$$ 表示魔盒的魔系数。第二行包含长度为$$$N$$$的字符串$$$S$$$。如果魔法石 $$$i$$$ 为黑色,$$$S_i$$$ 为 $$$0$$$;如果魔法石 $$$i$$$ 为白色,$$$1$$$ 为 $$$1$$$。如果有不止一种着色和选择魔法系数 $$$Z$$$ 的可能性,则输出其中任何一个。

示例

输入 #1

4
4 10 9 14

输出 #1

0
1001

注意

通过给出上面的着色,可以看出:

- $$$i=1, j=2 \longrightarrow \text{concat}(4, 10) \times \text{concat}(10, 4) + 10 \times 4 = 410 \times 104 + 40 = 42680 \equiv 2 \mod 3$$$
- $$$i=1, j=3 \longrightarrow \text{concat}(4, 9) \times \text{concat}(9, 4) + 4 \times 9 = 49 \times 94 + 36 = 4642 \equiv 1 \mod 3$$$
- $$$i=4, j=2 \longrightarrow \text{concat}(14, 10) \times \text{concat}(10, 14) + 10 \times 14 = 1410 \times 1014 + 140 = 1429880 \equiv 2 \mod 3$$$
- $$$i=4, j=3 \longrightarrow \text{concat}(14, 9) \times \text{concat}(9, 14) + 14 \times 9 = 149 \times 914 + 126 = 136312 \equiv 1 \mod 3$$$

因此,通过选择$$$Z = 0$$$,可以保证没有魔法石发生反应。