問題一覧 > 通常問題

No.1888 Odd Insertion

レベル : / AI推定難易度 : 2700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 11
作問者 : miscalc / テスター : first_vil ygussany
お気に入りにしたユーザー ProblemId : 7008 / 自分の提出
問題文最終更新日: 2022-03-17 20:36:45
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 337 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。