[Solution] Hot Black Hot White Codeforces Solution

H. Hot Black Hot White

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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$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≤𝑍≤2$0\le Z\le 2$). The painting of the magical stones must be done in a way such that there are 𝑁2$\frac{N}{2}$ black magical stones and 𝑁2$\frac{N}{2}$ white magical stones.

Define concat(𝑥,𝑦)$\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, concat(10,24)$\text{concat}(10,24)$ will result in 1024$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 concat(𝐴𝑖,𝐴𝑗)×concat(𝐴𝑗,𝐴𝑖)+𝐴𝑖×𝐴𝑗≡𝑍mod3$\text{concat}(A_i,A_j)\times \text{concat}(A_j,A_i)+A_i\times A_j\equiv Z\mathrm{mod}3$. A magical stone that is reacting will

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 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

The first line contains a single even integer 𝑁$N$ (2≤𝑁≤105$2\le N\le {10}^5$) — the number of magical stones Dr. Chanek has.

The second line contains 𝑁$N$ integer 𝐴1,𝐴2,…,𝐴𝑁$A_1,A_2,\dots ,A_N$ (1≤𝐴𝑖≤109$1\le A_i\le {10}^9$) — the strengths of all magical stones.

Output

If it is not possible to satisfy the condition of the problem, output −1$-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$0$ if magical stone 𝑖$i$ is coloured black or 1$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.