問題一覧 > 通常問題

No.1508 Avoid being hit

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 45
作問者 : 遭難者遭難者 / テスター : noya2noya2 oliverx3oliverx3 yuto1115yuto1115
1 ProblemId : 6213 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-15 01:05:48

問題文

横一列に並んだ $N$ 個のマスと $1$ つの駒があります。左から $i$ $(1\le i\le N)$ 番目のマスを $i$ のマスと呼びます。

あなたは遭難者君と一緒にこれらを使った以下のようなゲームをします。


最初にあなたが好きなマスに駒を置きます。

次にあなたを先手として交互に手番を $Q$ 回繰り返します。 $i$ 回目の手番は以下の通りです。

  • あなたの手番 : 現在の駒が $P$ のマスにあるとすると、駒を $P-1$ か $P$ か $P+1$ のマスに移動させる。 ただし、 $P=1$ の時は $1$ か $2$ のマスに、 $P=N$ の時は $N-1$ か $N$ のマスにしか移動させることはできない。

  • 遭難者君の手番 : $A_i$ のマスを叩いた後に、 $B_i$ のマスを叩く。もし叩いたマスに駒があるなら、その時点で遭難者君の勝ちである。

    • 全ての行動が終わった後に駒が遭難者君に叩かれていなかった場合、あなたの勝ちです。


    あなたがこのゲームに勝てるかどうかを判定し、もし勝てるならゲームに勝てるような駒の動かし方の例を $1$ つ出力してください。

    制約

  • $2\le N\le 10^5$
  • $1\le Q\le 10^5$
  • $1\le A_i\ ,\ B_i\le N$
  • 入力は全て整数である

    • 入力

    $N$ $Q$
$A_1\ \ldots\ A_Q$
$B_1\ \ldots\ B_Q$

    出力

    あなたがこのゲームに勝てる場合、以下のように $Q+2$ 行出力してください。 

    YES
$S$
$K_1$
$K_2$
$\vdots$
$K_Q$
    ただし、 $S$ はあなたが最初に駒を置いたマスで、 $K_i$ はあなたの $i$ 番目の手番で駒を動かした先のマスです。

    あなたがこのゲームに勝てない場合、以下のように $1$ 行出力してください。 
    NO

    サンプル

    サンプル1
    入力
    3 3
1 1 2
2 3 3
    出力
    YES
2
3
2
1

    例えばゲームは以下のように進行します。

    あなた : $2$ のマスに駒を置く。

    あなた : $3$ のマスに駒を動かす。

    遭難者 : $1$ のマスを叩いた後に、 $2$ のマスを叩く。駒を叩けていないので、ゲームは続行する。

    あなた : $2$ のマスに駒を動かす。

    遭難者 : $1$ のマスを叩いた後に、 $3$ のマスを叩く。駒を叩けていないので、ゲームは続行する。

    あなた : $1$ のマスに駒を動かす。

    遭難者 : $2$ のマスを叩いた後に、 $3$ のマスを叩く。駒を叩けていないので、ゲームは続行する。

    交互に手番を $Q=3$ 回繰り返した時点であなたは遭難者君に駒を叩かれていないので、この時点であなたの勝利となります。

    サンプル2
    入力
    2 3
1 2 1
2 1 1
    出力
    NO

    どこに駒を動かしても $1$ 回目の遭難者君の手番に叩かれるので、 NO を出力してください。

    $A_i> B_i$ となることや、 $A_i=B_i$ となるケースも存在することに注意してください。

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

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