No.930 数列圧縮
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 136
作問者 :
chocorusk
/ テスター :
risujiroh
タグ : / 解いたユーザー数 136
作問者 :
chocorusk
/ テスター :
risujiroh
問題文最終更新日: 2019-11-19 22:00:21
問題文
yuki君は長さ $N$ の数列 $a$ を持っています。$a$ は $1, 2, \ldots , N$ の順列です。yuki君は数列に次のような操作を行うことができます。
- 数列の隣りあう $2$ つの要素であって、(左の要素)$<$(右の要素) を満たすものを選び、そのどちらか一方を削除する。
入力
$N$ $a_1\ a_2\ \ldots \ a_N$
- $2\leq N\leq 10^5$
- $1\leq a_i\leq N$
- $i\neq j$ のとき $a_i\neq a_j$
- 入力はすべて整数である。
出力
操作により数列の長さを $1$ にすることが不可能なら、Noと出力せよ。可能なら、$1$ 行目にYesと出力し、$2$ 行目に $N-1$ 個の整数を空白区切りで出力せよ。$i$ 個目の整数は、$i$ 回目の操作で削除する数でなければならない。複数の手順が考えられる場合、どれを出力してもよい。
サンプル
サンプル1
入力
4 2 3 1 4
出力
Yes 2 1 4
- 隣りあう $2$ つの要素 $(2, 3)$ を選び、$2$ を削除します。数列は $(3, 1, 4)$ となります。
- 隣りあう $2$ つの要素 $(1, 4)$ を選び、$1$ を削除します。数列は $(3, 4)$ となります。
- 隣りあう $2$ つの要素 $(3, 4)$ を選び、$4$ を削除します。数列は $(3)$ となります。
サンプル2
入力
5 5 4 2 3 1
出力
No
- 最初に行える操作は、隣りあう $2$ つの要素 $(2, 3)$ を選び、$2$ または $3$ を削除する操作のみです。
- 最初に $2$ を削除すると、数列は $(5, 4, 3, 1)$ となり、これ以上操作を行えません。
- 最初に $3$ を削除すると、数列は $(5, 4, 2, 1)$ となり、これ以上操作を行えません。
サンプル3
入力
6 3 6 2 5 1 4
出力
Yes 1 5 6 2 4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。