Hot Black Hot White

题意翻译

#### 题目大意 Dr. Chanek 有 $n$ 块魔法石，编号为 $1$ 至 $n$。第 Dr. Chanek 有 $n$ 块魔法石，编号为 $1$ 至 $n$。第 $i$ 块魔法石拥有 $a_i$ 的力量。Dr. Chanek 需要将 $n$ 块魔法石中的 $\frac{n}{2}$ 块染成黑色，另外 $\frac{n}{2}$ 块染成白色。 当第 $i$ 块魔法石和第 $j$ 块魔法石同时满足以下两个条件时，它们就会发生反应： 1. $color_i \ne color_j$（即两块石头颜色不同） 2. $\text{concat}(a_i,a_j) \times \text{concat}(a_j,a_i) + a_i \times a_j \equiv Z \mod 3$（即 $(\text{concat}(a_i,a_j) \times \text{concat}(a_j,a_i) + a_i \times a_j) \mod 3 = Z \mod 3$） 其中 $\text{concat}(x,y)$ 表示将十进制下的 $x$ 接在十进制下的 $y$ 的左边形成的新十进制数。例如，$\text{concat}(10,24) = 1024$。 因为魔法石发生反应时会很热很危险，所以你需要确定 $Z$ 的值和魔法石的染色方案，使任意一对魔法石之间都不产生反应。 #### 输入格式 第一行，一个正整数 $n(2 \leq n \leq 10^5)$。 第二行，$n$ 个正整数，第 $i$ 个数表示 $a_i$。 #### 输出格式 如果不存在使魔法石不会发生反应的 $Z$ 和 染色方案，直接输出 $-1$。 否则，第一行，输出一个数 $Z$。 第二行，输出一个长度为 $n$ 的字符串 $s$。其中，$s_i = 0$ 表示第 $i$ 块魔法石染成黑色，$s_i = 1$ 表示第 $i$ 块魔法石染成白色。 （Translated by @[owo_ImposterAnYu_owo](https://www.luogu.com.cn/user/510555)）

题目描述

One day, you are accepted as being Dr. Chanek's assistant. The first task given by Dr. Chanek to you is to take care and store his magical stones. Dr. Chanek has $ N $ magical stones with $ N $ being an even number. Those magical stones are numbered from $ 1 $ to $ N $ . Magical stone $ i $ has a strength of $ A_i $ . A magical stone can be painted with two colours, namely the colour black or the colour white. You are tasked to paint the magical stones with the colour black or white and store the magical stones into a magic box with a magic coefficient $ Z $ ( $ 0 \leq Z \leq 2 $ ). The painting of the magical stones must be done in a way such that there are $ \frac{N}{2} $ black magical stones and $ \frac{N}{2} $ white magical stones. Define $ \text{concat}(x, y) $ for two integers $ x $ and $ y $ as the result of concatenating the digits of $ x $ to the left of $ y $ in their decimal representation without changing the order. As an example, $ \text{concat}(10, 24) $ will result in $ 1024 $ . For a magic box with a magic coefficient $ Z $ , magical stone $ i $ will react with magical stone $ j $ if the colours of both stones are different and $ \text{concat}(A_i, A_j) \times \text{concat}(A_j, A_i) + A_i \times A_j \equiv Z \mod 3 $ . A magical stone that is reacting will be very hot and dangerous. Because of that, you must colour the magical stones and determine the magic coefficient $ Z $ of the magic box in a way such that there is no magical stone that reacts, or report if it is impossible.

输入输出格式

输入格式

The first line contains a single even integer $ N $ ( $ 2 \le N \le 10^5 $ ) — the number of magical stones Dr. Chanek has. The second line contains $ N $ integer $ A_1, A_2, \ldots, A_N $ ( $ 1 \leq A_i \leq 10^9 $ ) — the strengths of all magical stones.

输出格式

If it is not possible to satisfy the condition of the problem, output $ -1 $ . Otherwise, output two lines. The first line contains an integer $ Z $ denoting the magic coefficient of the magic box. The second line contains a string $ S $ of length $ N $ . $ S_i $ is $ 0 $ if magical stone $ i $ is coloured black or $ 1 $ if magical stone $ i $ is coloured white. If there are more than one possibilities of colouring and choosing the magic coefficient $ Z $ , output any of them.

输入输出样例

输入样例 #1

4
4 10 9 14

输出样例 #1

0
1001

说明

By giving the above colouring, it can be seen that: - $ 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 $ Because of that, by choosing $ Z = 0 $ , it can be guaranteed that there is no magical stone that reacts.

**题目大意**：

Chanek博士有 $ n $ 块魔法石，编号为 $ 1 $ 到 $ n $。第 $ i $ 块魔法石的力量为 $ a_i $。Chanek博士需要将这 $ n $ 块魔法石中的 $ \frac{n}{2} $ 块染成黑色，另外 $ \frac{n}{2} $ 块染成白色。

当第 $ i $ 块和第 $ j $ 块魔法石同时满足以下两个条件时，它们会发生反应：

1. $ color_i \neq color_j $（即两块石头颜色不同）
2. $ \text{concat}(a_i,a_j) \times \text{concat}(a_j,a_i) + a_i \times a_j \equiv Z \mod 3 $（即 $ (\text{concat}(a_i,a_j) \times \text{concat}(a_j,a_i) + a_i \times a_j) \mod 3 = Z \mod 3 $）

其中 $ \text{concat}(x,y) $ 表示将十进制下的 $ x $ 接在十进制下的 $ y $ 的左边形成的新十进制数。例如，$ \text{concat}(10,24) = 1024 $。

因为魔法石发生反应时会很热很危险，所以需要确定 $ Z $ 的值和魔法石的染色方案，使任意一对魔法石之间都不产生反应。

**输入格式**：

第一行，一个正整数 $ n (2 \leq n \leq 10^5) $。

第二行，$ n $ 个正整数，第 $ i $ 个数表示 $ a_i $。

**输出格式**：

如果不存在使魔法石不会发生反应的 $ Z $ 和 染色方案，直接输出 $ -1 $。

否则，第一行，输出一个数 $ Z $。

第二行，输出一个长度为 $ n $ 的字符串 $ s $。其中，$ s_i = 0 $ 表示第 $ i $ 块魔法石染成黑色，$ s_i = 1 $ 表示第 $ i $ 块魔法石染成白色。**题目大意**： Chanek博士有 $ n $ 块魔法石，编号为 $ 1 $ 到 $ n $。第 $ i $ 块魔法石的力量为 $ a_i $。Chanek博士需要将这 $ n $ 块魔法石中的 $ \frac{n}{2} $ 块染成黑色，另外 $ \frac{n}{2} $ 块染成白色。 当第 $ i $ 块和第 $ j $ 块魔法石同时满足以下两个条件时，它们会发生反应： 1. $ color_i \neq color_j $（即两块石头颜色不同） 2. $ \text{concat}(a_i,a_j) \times \text{concat}(a_j,a_i) + a_i \times a_j \equiv Z \mod 3 $（即 $ (\text{concat}(a_i,a_j) \times \text{concat}(a_j,a_i) + a_i \times a_j) \mod 3 = Z \mod 3 $） 其中 $ \text{concat}(x,y) $ 表示将十进制下的 $ x $ 接在十进制下的 $ y $ 的左边形成的新十进制数。例如，$ \text{concat}(10,24) = 1024 $。 因为魔法石发生反应时会很热很危险，所以需要确定 $ Z $ 的值和魔法石的染色方案，使任意一对魔法石之间都不产生反应。 **输入格式**： 第一行，一个正整数 $ n (2 \leq n \leq 10^5) $。 第二行，$ n $ 个正整数，第 $ i $ 个数表示 $ a_i $。 **输出格式**： 如果不存在使魔法石不会发生反应的 $ Z $ 和 染色方案，直接输出 $ -1 $。 否则，第一行，输出一个数 $ Z $。 第二行，输出一个长度为 $ n $ 的字符串 $ s $。其中，$ s_i = 0 $ 表示第 $ i $ 块魔法石染成黑色，$ s_i = 1 $ 表示第 $ i $ 块魔法石染成白色。