P5584 "SWTR-1" Sunny's Crystals

Little $\mathrm{S}$ likes collecting crystals.

Little $\mathrm{S}$ has $n$ crystals. Each crystal has an attribute $d_i$, which is the **value** of this crystal. One day, Little $\mathrm{A}$ came to Little $\mathrm{S}$'s home and asked Little $\mathrm{S}$ to arrange the crystals into a sequence, and destroy all crystals whose value is $w$. However, due to the special property of this sequence, each destruction must satisfy: - The crystal's position in the sequence **must be a power of $2$**. That is, you can only destroy crystals at position $2^x$, where $0 \leq x \leq \log_2 y$ and $x$ is an integer, and $y$ is the current number of crystals in the sequence. After destroying one crystal, **all crystals after it move forward by one position**. For example, for the value sequence $6\ 10\ 4\ 7\ 8$, you can only destroy crystals at positions $1,2,4$. If you destroy the crystal at position $2$, the sequence becomes $6\ 4\ 7\ 8$. To save time, Little $\mathrm{S}$ wants to know the **minimum** number of destructions needed to destroy all crystals with value $w$, and what the initial position of the destroyed crystal is for the $i$-th destruction. **This problem uses Special Judge**. If there are multiple answers, you may output any one of them.

The first line contains two integers $n,w$. The second line contains $n$ positive integers $d_i$.

The first line contains an integer $m$, meaning the minimum number of destructions needed to destroy all crystals with value $w$. The next line contains $m$ numbers. The $i$-th number indicates the **initial position** of the crystal destroyed in the $i$-th destruction, **separated by spaces**.

--- ### Sample Explanation Sample $1$: First destroy the later $4$, whose initial position is $4$. The **value** sequence becomes: $1\ 4\ 2\ 5$. Then destroy the earlier $4$, whose initial position is $2$. The total number of destructions is $2$. Sample $2$: First destroy the first $2$, whose initial position is $2$, and the sequence becomes: $1\ 2\ 2\ 2$. Then destroy the remaining first $2$, whose initial position is $3$, and the sequence becomes: $1\ 2\ 2$. Then destroy the first $2$, whose initial position is $4$, and the sequence becomes: $1\ 2$. Then destroy the first $2$, whose initial position is $5$. The total number of destructions is $4$. --- ### Constraints and Notes For $15\%$ of the testdata, $n \leq 5$. For $25\%$ of the testdata, $n \leq 20$. For $30\%$ of the testdata, $n \leq 1000$. For $35\%$ of the testdata, $n \leq 10000$. For $50\%$ of the testdata, $n \leq 3 \times 10^5$. For $80\%$ of the testdata, $n \leq 10^6$. For $100\%$ of the testdata, $1 \leq n \leq 3 \times 10^6, 1 \leq d_i \leq 40000$. It is guaranteed that the number of $w$ is no more than $1.5 \times 10^6$. --- The shattered crystals sparkle under the sunlight... Translated by ChatGPT 5