No.930 数列圧縮

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 79
作問者 : chocoruskchocorusk / テスター : risujirohrisujiroh
14 ProblemId : 2878 / 出題時の順位表
問題文最終更新日: 2019-11-19 22:00:21

問題文

yuki君は長さ $N$ の数列 $a$ を持っています。$a$ は $1, 2, \ldots , N$ の順列です。yuki君は数列に次のような操作を行うことができます。

  • 数列の隣りあう $2$ つの要素であって、(左の要素)$<$(右の要素) を満たすものを選び、そのどちらか一方を削除する。
数列 $a$ に $N-1$ 回操作を行って数列の長さを $1$ にすることができるか判定し、できるならその手順をひとつ求めてください。

入力

$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)$ となり、これ以上操作を行えません。
よって、数列の長さを $1$ にすることは不可能です。

サンプル3
入力
6
3 6 2 5 1 4
出力
Yes
1 5 6 2 4

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。