P9139 [THUPC 2023 Preliminary] Meow Meow II

Originally, this problem statement was related to "Meow Meow". But I heard some people thought the statement was too long, so let’s keep it short.

You are given a sequence of length $4n$, where each number from $1$ to $n$ appears exactly $4$ times. Determine whether it is possible to split it into two identical subsequences of equal length.

The first line contains a positive integer $n$. The second line contains $4n$ positive integers describing the sequence. It is guaranteed that each number from $1$ to $n$ appears exactly $4$ times.

If it is impossible to split into two identical subsequences, output one line `No`. Otherwise, output `Yes` on the first line. On the second line, output a `01` string of length $4n$. The $i$-th character indicates which subsequence the $i$-th number of the original sequence is assigned to. You must ensure that the two subsequences you obtain are exactly identical.

#### Sample Explanation 1 Both subsequences are $(1,2,1,2)$. #### Subtasks Constraints: $1\le n \le 5\times10^4$. It is guaranteed that each number from $1$ to $n$ appears exactly $4$ times in the sequence. #### Scoring The first line of your output must match the standard answer. If it is `Yes`, any valid splitting is accepted. #### Source From the preliminary round of the 2023 Tsinghua University Student Algorithm and Programming Contest and Collegiate Invitational (THUPC2023). Resources such as editorials can be found at . By E.Space: Since the testdata was too weak during the contest, the testdata for this problem has been strengthened. Translated by ChatGPT 5