問題一覧 > 通常問題

No.1508 Avoid being hit

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （AC するまで非表示） / 解いたユーザー数 44
作問者 : 👑 qand / テスター : noya2 oliverx3 yuto1115
お気に入りにしたユーザー ProblemId : 6213 / 自分の提出
問題文最終更新日: 2021-05-15 01:05:48
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 295 (順位表) の他の問題:

Problem Statement

There are $N$ squares arranged in a row and $1$ piece. The $i$-th $(1\le i\le N)$ square from the left is called square $i$.

You play the following game with Sonansha-kun using these.


First, you place the piece on any square you like.

Then, with you going first, you take turns alternately, repeating this $Q$ times. The $i$-th round of turns is as follows.

  • Your turn: If the piece is currently on square $P$, move the piece to square $P-1$, $P$, or $P+1$. However, when $P=1$, it can only be moved to square $1$ or $2$, and when $P=N$, it can only be moved to square $N-1$ or $N$.

  • Sonansha-kun's turn: He hits square $A_i$, and then hits square $B_i$. If the piece is on a square that he hits, Sonansha-kun wins at that point.

    • If the piece has not been hit by Sonansha-kun after all actions are finished, you win.


    Determine whether you can win this game, and if you can, output $1$ example of how to move the piece so that you win the game.

    Constraints

  • $2\le N\le 10^5$
  • $1\le Q\le 10^5$
  • $1\le A_i\ ,\ B_i\le N$
  • All inputs are integers.

    • Input

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

    Output

    If you can win this game, output $Q+2$ lines as follows. 

    YES
$S$
$K_1$
$K_2$
$\vdots$
$K_Q$
    Here, $S$ is the square on which you first placed the piece, and $K_i$ is the square to which you moved the piece on your $i$-th turn.

    If you cannot win this game, output $1$ line as follows. 
    NO

    Sample

    Sample 1
    Input
    3 3
1 1 2
2 3 3
    Output
    YES
2
3
2
1

    For example, the game proceeds as follows.

    You: Place the piece on square $2$.

    You: Move the piece to square $3$.

    Sonansha: Hits square $1$, and then hits square $2$. The piece has not been hit, so the game continues.

    You: Move the piece to square $2$.

    Sonansha: Hits square $1$, and then hits square $3$. The piece has not been hit, so the game continues.

    You: Move the piece to square $1$.

    Sonansha: Hits square $2$, and then hits square $3$. The piece has not been hit, so the game continues.

    At the point when the alternating turns have been repeated $Q=3$ times, your piece has not been hit by Sonansha-kun, so you win at this point.

    Sample 2
    Input
    2 3
1 2 1
2 1 1
    Output
    NO

    Wherever you move the piece, it is hit on Sonansha-kun's turn number $1$, so output NO.

    Note that there are also cases where $A_i> B_i$ and cases where $A_i=B_i$.

    Sample 3
    Input
    4 5
2 1 3 1 2
3 4 4 2 3
    Output
    YES
3
4
3
2
3
4

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