問題一覧 > 通常問題

No.930 Sequence Compression

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （AC するまで非表示） / 解いたユーザー数 143
作問者 : chocorusk / テスター : risujiroh
お気に入りにしたユーザー ProblemId : 2878 / 自分の提出
問題文最終更新日: 2019-11-19 22:00:21
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 231 (順位表) の他の問題:

Problem Statement

Yuki has a sequence $a$ of length $N$. $a$ is a permutation of $1, 2, \ldots , N$. Yuki can perform the following operation on the sequence.

  • Choose $2$ adjacent elements of the sequence satisfying (left element)$<$(right element), and delete one of them.
Determine whether the length of the sequence $a$ can be made $1$ by performing the operation $N-1$ times, and if it can, find one such procedure.

Input

$N$
$a_1\ a_2\ \ldots \ a_N$

  • $2\leq N\leq 10^5$
  • $1\leq a_i\leq N$
  • If $i\neq j$, then $a_i\neq a_j$
  • All inputs are integers.

Output

If it is impossible to make the length of the sequence $1$ by the operations, print No. If it is possible, print Yes on line $1$, and on line $2$ print $N-1$ space-separated integers. The $i$-th integer must be the number to delete in the $i$-th operation. If there are multiple possible procedures, you may print any of them.

Sample

Sample 1
Input
4
2 3 1 4
Output
Yes
2 1 4

  • Choose the $2$ adjacent elements $(2, 3)$ and delete $2$. The sequence becomes $(3, 1, 4)$.
  • Choose the $2$ adjacent elements $(1, 4)$ and delete $1$. The sequence becomes $(3, 4)$.
  • Choose the $2$ adjacent elements $(3, 4)$ and delete $4$. The sequence becomes $(3)$.

Sample 2
Input
5
5 4 2 3 1
Output
No

  • The only operation that can be performed first is to choose the $2$ adjacent elements $(2, 3)$ and delete $2$ or $3$.
  • If $2$ is deleted first, the sequence becomes $(5, 4, 3, 1)$, and no further operations can be performed.
  • If $3$ is deleted first, the sequence becomes $(5, 4, 2, 1)$, and no further operations can be performed.
Therefore, it is impossible to make the length of the sequence $1$.

Sample 3
Input
6
3 6 2 5 1 4
Output
Yes
1 5 6 2 4

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。