Hot Black Hot White
Contest: COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1800
Tags: constructive algorithms, math

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
4
4 10 9 14

Example output:
0
1001

Editorial:
Notice that $$$10 \equiv 1 \mod 3$$$. Hence, if $$$k$$$ denotes the number of digits in $$$A_j$$$, $$$\text{concat}(A_i, A_j) \mod 3= (A_i \times 10^k + A_j) \mod 3 = (A_i \times 1^k + A_j) \mod 3 = (A_i + A_j) \mod 3$$$.
Then one can simplify the equation that determines the reaction of stone $$$i$$$ and stone $$$j$$$ as follows. $$$$$$ \begin{align} \text{concat}(A_i, A_j) \times \text{concat}(A_j, A_i) + A_i A_j & \equiv Z \mod 3 \\ (A_i + A_j) (A_i + A_j) + A_i A_j & \equiv Z \mod 3 \\ A_i^2 + 2 A_i A_j + A_j^2 + A_i A_j & \equiv Z \mod 3 \\ A_i^2 + A_j^2 + 3 A_i A_j & \equiv Z \mod 3 \\ A_i^2 + A_j^2 & \equiv Z \mod 3 \\ \end{align} $$$$$$ One can see that:
• $$$0^2 = 0 \equiv 0 \mod 3$$$.
• $$$1^2 = 1 \equiv 1 \mod 3$$$.
• $$$2^2 = 4 \equiv 1 \mod 3$$$.
So the value of $$$A_i^2 \mod 3$$$ is either $$$0$$$ or $$$1$$$.
We can get a construction that consists of the two following cases:
• If there are at least $$$\frac{N}{2}$$$ stones having $$$A_i^2 \equiv 0 \mod 3$$$, then we can colour the stones such that one of the colours only occurs in all stones with $$$A_i^2 \equiv 0 \mod 3$$$. In this construction, there is no pair of stones with different colours that both have $$$A_i^2 \equiv 1 \mod 3$$$. So we can assign $$$Z=2$$$.
• If there are less than $$$\frac{N}{2}$$$ stones having $$$A_i^2 \equiv 0 \mod 3$$$, then there are at least $$$\frac{N}{2}$$$ stones having $$$A_i^2 \equiv 1 \mod 3$$$, so we can colour the stones such that one of the colours only occurs in all stones with $$$A_i^2 \equiv 1 \mod 3$$$. In this construction, there is no pair of stones with different colours that both have $$$A_i^2 \equiv 0 \mod 3$$$. So we can assign $$$Z=0$$$.
Time complexity: $$$O(N)$$$