問題一覧 > 通常問題

No.1370 置換門松列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 71
作問者 : maimai / テスター : QCFiumQCFium
15 ProblemId : 3118 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-11-05 23:39:32

定義

3つの要素から成る数列$v = (a_1,a_2,a_3)$が次の条件を満たす時、$v$は門松列であると言い伝えられています。

  1. $a_1,a_2,a_3$は全て異なる
  2. 3つの要素のうち$a_2$が最も大きい、あるいは最も小さい

さらに、$n$個の要素(ただし$3\le n$)から成る数列$w = (a_1,...,a_n)$が
どの連続した3つの要素を取り出しても門松列であるとき $w$は門松列列であると言います。

問題文

数列 $x_{a_1}, x_{a_2}, \ldots, x_{a_N}$ が門松列列となるような、$x_1, x_2, \ldots, x_M$ の割り当てが存在するかどうか判定し、存在するならば1つ出力してください。

入力

$N$ $M$
$a_1$ .. $a_N$

$3 \le N \le 10^5$
$1 \le M \le 10^5$
$1 \le a_i \le M$
入力に含まれる値はすべて整数である

出力

条件を満たす割り当てが存在しないなら、Noを出力してください。

存在するならば、Yesを出力後、改行区切りまたは半角スペース区切りで $x_1, x_2, \ldots, x_M$ を出力してください。
$1 \le x_i \le 10^9$ の制約を満たす整数である必要があります。

スペシャルジャッジです。解は複数存在しますが、どれを出力しても構いません。

サンプル

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

出力の通りに割り当てると、2 3 1 2になります。これは門松列列ですね。

4 3 5を出力してもokです。

サンプル2
入力
5 3
1 3 3 3 1
出力
No

使っていない変数があるかもしれません

サンプル3
入力
6 3
1 2 3 1 2 3
出力
No

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

サンプルの出力はあくまでも一例です。解は複数存在します。

サンプル5
入力
3 2
2 1 2
出力
No

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