P11066 [MX-X4-T6] "Jason-1" Elevator.

Original link: .

A building with $n$ floors has $m$ elevators. Each elevator can be in two states: stationary or moving. Initially, elevator $i$ is stationary on floor $i$. Given a permutation $p$ of $1 \sim m$, you want elevator $i$ to end up on floor $p_i$. You can perform the following two types of operations: - `0`: Move time forward by one moment. - `x`: where $x$ is a positive integer not exceeding $n$. - To perform this operation, the following must hold: there is no stationary elevator on floor $x$; the stationary elevator that is closest$^\dagger$ to floor $x$ exists and is unique. - Let $y$ be the index of the nearest stationary elevator, and $z$ be its position. Then elevator $y$ **immediately** becomes a moving elevator, and it will arrive at floor $x$ and become stationary **before all operations** after $\lvert x - z\rvert$ moments. $^\dagger$: The distance between an elevator located on floor $a$ and floor $x$ is $\lvert a - x\rvert$. **Note: You must ensure that at any time, there are not two stationary elevators on the same floor.** For each testdata, there is a scoring parameter $o$. You must construct a plan whose total number of operations does not exceed $o$ in order to pass that testdata. This problem uses a **custom checker** to verify whether your answer is correct. Therefore, if there are multiple valid plans, you only need to output **any one**.

**This problem input contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. For each test case: - The first line contains four positive integers $Q, n, m, o$, representing the number of queries, the number of floors, the number of elevators, and the scoring parameter. - The next $Q$ lines each contain $m$ integers $p_1, \ldots, p_m$, representing the target positions of the elevators.

For each test case: - Output a total of $2 Q$ lines. For each query, output two lines: - The first line contains a non-negative integer $k$, the number of operations in your plan. - The second line contains $k$ integers in $[0, n]$, representing your specific sequence of operations. This problem uses a **custom checker** to verify whether your answer is correct. Therefore, if there are multiple valid plans, you only need to output **any one**.

**[Sample Explanation #1]** This sample satisfies the constraints of Subtask 2. For the first query of the first test case, no operation is needed. For the second query of the first test case: | Operation | Time | Elevator $1$ Position | Elevator $2$ Position | | :----------: | :----------: | :----------: | :----------: | | Initial state | $0$ | $1$ | $2$ | | $3$ | $0$ | $1$ | moving | | $4$ | $0$ | moving | moving | | $0$ | $1$ | moving | $3$ | | $0$ | $2$ | moving | $3$ | | $1$ | $2$ | moving | moving | | $0$ | $3$ | $4$ | moving | | $2$ | $3$ | moving | moving | | $0$ | $4$ | moving | $1$ | | $0$ | $5$ | $2$ | $1$ | **[Sample Explanation #2]** This sample satisfies the constraints of Subtask 7. **[Constraints]** **This problem uses bundled test.** | Subtask | $n \le$ | $m =$ | $o = $ | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | $3$ | $2$ | $7$ | $7$ | | 2 | $100$ | $\lfloor \frac{n}{2} \rfloor$ | $2\times(m+n)$ | $11$ | | 3 | $40$ | $n-1$ | $3 \times n^3$ | $17$ | | 4 | $200$ | $n-1$ | $5 \times n^2$ | $19$ | | 5 | $4000$ | $n-1$ | $50 \times n$ | $17$ | | 6 | $5 \times 10^{4}$ | $n-1$ | $6 \times n$ | $16$ | | 7 | $5 \times 10^{4}$ | $n-1$ | $5 \times n$ | $13$ | For all testdata, $1 \le T \le 20$, $2 \le m < n \le 5 \times 10^{4}$. It is guaranteed that $n, m, o$ simultaneously satisfy the constraints of some subtask above. $p$ is a permutation of $1 \sim m$. $1 \le Q \le 2\times 10^6$, $\sum o Q \le 2 \times 10^6$. Translated by ChatGPT 5