P15345 [TOIP 2025] Consecutive Ones

The binary representation of a non-negative integer can be viewed as a $01$ string, with the left side being the most significant bit and the right side being the least significant bit. If it has at most $k$ consecutive bits equal to $1$, then the number’s “consecutive order” is defined as $k$. Given $n$ non-negative integers, sort them in increasing order of their “consecutive order”. If two numbers have the same consecutive order, output the one with the smaller value first. For example, the binary representations of $7$, $12$, and $27$ are ${\left(111\right)}_2$, ${\left(1100\right)}_2$, and ${\left(11011\right)}_2$, respectively. Their consecutive orders are $3$, $2$, and $2$. Since $12$ and $27$ have the same consecutive order but $12 < 27$, the output should be, in order, $12$, $27$, $7$.

$$ \begin{aligned} &n \\ &a_1 \; a_2 \; a_3 \; \cdots \; a_n \end{aligned} $$ * $n$ is the number of integers to be sorted. * $a_i$ is the $i$-th integer to be sorted.

$$ \begin{aligned} &s_1 \; s_2 \; s_3 \; \cdots \; s_n \end{aligned} $$ * $s_i$ is the $i$-th integer after sorting according to the requirements.

### Constraints * $1 \le n \le 2 \times {10}^5$. * $0 \le a_i < 2^{30}$. * All input numbers are integers. ### Scoring This problem has four subtasks with the following constraints. Each subtask may contain one or more testdata files. You will get the score for a subtask only if you answer all testdata files in that subtask correctly. | Subtask | Score | Additional Input Constraints | | :-----: | :---: | ---------------------------- | | 1 | 22 | $n \le 2,\ a_i < 16$。 | | 2 | 22 | $n \le 2\,000,\ a_i < 2^{16}$。 | | 3 | 26 | $a_i < 2^{16}$。 | | 4 | 30 | No additional constraints. | Translated by ChatGPT 5