## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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$ 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\le Z\le 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}\left(x,y\right)$ 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}\left(10,24\right)$ 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}\left({A}_{i},{A}_{j}\right)×\text{concat}\left({A}_{j},{A}_{i}\right)+{A}_{i}×{A}_{j}\equiv Z\phantom{\rule{0.667em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}3$. A magical stone that is reacting will

Solution Click Below:-  👉
👇👇👇👇👇

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\le N\le {10}^{5}$) — the number of magical stones Dr. Chanek has.

The second line contains $N$ integer ${A}_{1},{A}_{2},\dots ,{A}_{N}$ ($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$.

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.