No.3211 NAND Oracle
タグ : / 解いたユーザー数 72
作問者 : 👑

問題文
ループさんは $0$ または $1$ からなる長さ $2$ の数列 $A = (A_1, A_2)$ を隠し持っています。この $A$ は入力から与えられないことに注意してください。
あなたは $A$ に対し、以下の操作をちょうど $Q$ 回繰り返します。ここで、$n$ は各操作の直前における $A$ の長さを表します。
- $1 \leq i \lt j \leq n$ を満たす整数の組 $(i, j)$ を選ぶ。 $A$ の末尾に $A_i ~\overline{\land}~ A_j$ を挿入する。
ここで否定論理積 $\overline{\land}$ は、次を満たす二項演算であると定義されます。
- $0 ~ \overline{\land} ~ 0 = 0 ~ \overline{\land} ~ 1 = 1 ~ \overline{\land} ~ 0 = 1$
- $1 ~ \overline{\land} ~ 1 = 0$
ループさんの隠し持っている $A$ がいかなるものであっても、操作後の $A$ の総和が $K$ 以下となるような操作が存在するか判定してください。
存在するとき、その操作を $1$ つ提示してください。
制約
- $1 \leq Q \leq 2 \times 10^5$
- $2 \leq K \leq Q + 2$
- $Q, K$ は整数
入力
入力は以下の形式で標準入力から与えられます。
$Q$ $K$
出力
題意を満たす操作が存在するとき Yes
、存在しないとき No
を出力してください。
さらに Yes
であった場合、改行した後以下の形式で操作を出力してください。
$i_1$ $j_1$ $i_2$ $j_2$ $\vdots$ $i_Q$ $j_Q$
ここで、$i_k, j_k$ は $k$ 回目 $(1 \leq k \leq Q)$ の操作で選ぶ $i, j$ を表します。
正答が複数存在する場合、そのいずれを出力しても正解と判定されます。
サンプル
サンプル1
入力
3 3
出力
Yes 1 2 2 3 1 4
例えば、ループさんが $A = (1, 0)$ を隠し持っていた場合、以下の流れで操作が進みます。
- $(i, j) = (1, 2)$ を選ぶ。$1 ~ \overline{\land} ~ 0 = 1$ であるため、$A$ は $(1, 0, 1)$ に更新される。
- $(i, j) = (2, 3)$ を選ぶ。$0 ~ \overline{\land} ~ 1 = 1$ であるため、$A$ は $(1, 0, 1, 1)$ に更新される。
- $(i, j) = (1, 4)$ を選ぶ。$1 ~ \overline{\land} ~ 1 = 0$ であるため、$A$ は $(1, 0, 1, 1, 0)$ に更新される。
このとき、$A$ の総和は $3$ であり、$K = 3$ 以下となります。これは、ループさんがはじめにどのような $A$ を隠し持っていても成り立つことが示せます。
サンプル2
入力
4 2
出力
No
$Q = 4, ~ K = 2$ のとき、条件を満たす操作が存在しません。
サンプル3
入力
9 6
出力
Yes 1 2 1 2 1 2 1 2 3 4 3 5 3 6 4 5 7 8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。