No.3766 PQ Disjunction
レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限
: 1024 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 18
作問者 :
apricity
/ テスター :
👑 
AngrySadEight
タグ : / 解いたユーザー数 18
作問者 :
apricity
/ テスター :
👑
問題文最終更新日: 2026-09-10 22:41:57
yukicoder contest 518
(順位表)
の他の問題:
問題文
正整数 $N$ と非負整数 $K$ が与えられます． $\color{red}(0,1,\dots,N-1)$ の順列の二つ組 $(P = (P_1, P_2,\dots, P_N), Q = (Q_1, Q_2,\dots, Q_N))$ であって，次の条件を満たすものが存在するか判定し，存在する場合はその一例を示してください．
- $\displaystyle\bigvee_{i=1}^{N}\ (P_i \land Q_i) = K$.
$\land$ は bit ごとの論理積を表します． $\displaystyle\bigvee_{i=1}^{N}$ は $i=1,\dots,N$ に対する bit ごとの論理和を表します．
入力
$N\ K$
- 入力はすべて整数．
- $1 \leq N \leq 2\times 10^5$
- $0 \leq K < 2^{18}$
出力
条件を満たす組 $(P,Q)$ が存在しない場合， No と出力してください．
存在する場合，1行目に Yes を，2行目に $P$ を，3行目に $Q$ を，以下の形式に従って出力してください．
Yes $P_1\ P_2\ \dots\ P_N$ $Q_1\ Q_2\ \dots\ Q_N$
条件を満たす組が複数存在する場合，どれを出力しても正解とみなされます．
サンプル
サンプル1
入力
4 2
出力
Yes 2 3 0 1 3 2 1 0
bit ごとの論理和の二項演算子を $\lor$ と表記します． $P = (2,3,0,1), Q = (3,2,1,0)$ に対して $\bigvee_{i=1}^{N}\ (P_i \land Q_i) = (2\land 3) \lor (3 \land 2) \lor (0 \land 1) \lor (1 \land 0) = 2 \lor 2 \lor 0 \lor 0 = 2$ であり，確かに条件を満たしています．
サンプル2
入力
6 10
出力
No
条件を満たす組 $(P,Q)$ は存在しません．
サンプル3
入力
9 12
出力
Yes 0 1 2 3 4 5 6 7 8 3 6 1 0 7 2 5 4 8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。