32734번 - Anti-Closed Subsequences 스페셜 저지다국어

We consider a set of integers $S$ to be anti-closed if there do not exist elements $x$, $y$ and $z$ in $S$ where $x+y=z$ ($x$, $y$ and $z$ do not necessarily have to be distinct).

For example:

• $\{2, 3, 7\}$ is anti-closed, because no such $x$, $y$, $z$ exist
• $\{1, 3, 7, 10\}$ is not anti-closed, because $3$, $7$, and $10$ are all in the set and $3+7=10$
• $\{2, 4\}$ is also not anti-closed, because $2$ and $4$ are in the set and $2+2=4$

You are given an array $a$ of $n$ distinct integers. Partition it into at most $60$ anti-closed subsequences. Formally, find an array $b$ of size $n$ such that

• $1 \leq b_i \leq 60$ for all $1 \le i \le n$
• For each $1 \le x \le 60$, the subsequence of $a$ containing all values at indices $i$ where $b_i = x$ is anti-closed (The empty subsequence is considered anti-closed)

It can be shown that a solution always exists.

The first line of the input contains a single integer $n$ ($1 \le n \le 10^4$) --- the size of the array $a$.

The next line of the input contains $n$ distinct integers $a_1, a_2 \cdots a_n$ ($1 \le a_i \le 10^{18}$) --- the elements of the array $a$.

Output $n$ integers $b_1, b_2, \cdots b_n$ ($1 \le b_i \le 60$), representing the partition of $a$, as described above.

If there are multiple solutions, print any.

For the first test case, the input array is partitioned into these subsequences:

• $b_i = 1$: $\{1, 4, 6, 15\}$
• $b_i = 2$: $\{2, 3, 9, 10, 14\}$
• $b_i = 3$: $\{5, 7, 8\}$
• $b_i = 4$: $\{11, 12, 13\}$

We can show that each of these sets is anti-closed.