No.1888 Odd Insertion
Problem Statement
miscalc has a set $S = \{1, 2, \ldots, N\}$ and an empty sequence $A$. He performs $N$ operations on them. In the $i$-th operation, he does the following in order.
-
From those of the following that exist, choose $1$, and let $x$ be the chosen one.
- The smallest element contained in $S$
- The $2$-nd smallest element contained in $S$
- Choose an odd number $y$ satisfying $1 \leq y \leq i$.
- Remove $x$ from $S$ and insert it at the $y$-th position from the front of $A$.
Determine whether it is possible to make $A$ equal to $P = (P_1, P_2, \ldots, P_N)$ after all operations are completed, and if it is possible, show one example of such a sequence of operations.
Input
$N$ $P_1$ $P_2$ $\ldots$ $P_N$
- All input values are integers
- $1 \leq N \leq 2 \times 10^5$
- $P$ is a permutation of $(1, 2, \ldots, N)$
Output
If it is impossible to make $A$ equal to $P$, print No.
If it is possible to make $A$ equal to $P$, let $x_i, y_i$ be the $x, y$ chosen in the $i$-th operation, respectively, and print the sequence of operations in the following format.
Yes $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_N$ $y_N$
If there are multiple sequences of operations satisfying the conditions, you may print any of them.
Sample
Sample 1
Input
4 3 1 4 2
Output
Yes 1 1 3 1 2 3 4 3
With the operations in the output, $S$ and $A$ change as follows.
- Initially, $S = \{1, 2, 3, 4 \}, A = ()$.
- Choose $x = 1, y = 1$. It becomes $S = \{2, 3, 4 \}, A = (1)$.
- Choose $x = 3, y = 1$. It becomes $S = \{2, 4 \}, A = (3, 1)$.
- Choose $x = 2, y = 3$. It becomes $S = \{4 \}, A = (3, 1, 2)$.
- Choose $x = 4, y = 3$. It becomes $S = \{ \}, A = (3, 1, 4, 2)$.
Other outputs, such as the following, are also considered correct.
Yes 2 1 1 1 3 1 4 3
Sample 2
Input
4 1 4 2 3
Output
No
It is impossible to make $A = (1, 4, 2, 3)$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
miscalc