No.3766 PQ Disjunction
タグ : / 解いたユーザー数 19
作問者 :
apricity
/ テスター :
👑 Problem Statement
You are given a positive integer $N$ and a non-negative integer $K$. Determine whether there exists a pair $(P = (P_1, P_2,\dots, P_N), Q = (Q_1, Q_2,\dots, Q_N))$ of permutations of $\color{red}(0,1,\dots,N-1)$ satisfying the following condition, and if one exists, show an example.
- $\displaystyle\bigvee_{i=1}^{N}\ (P_i \land Q_i) = K$.
$\land$ denotes the bitwise AND. $\displaystyle\bigvee_{i=1}^{N}$ denotes the bitwise OR over $i=1,\dots,N$.
Input
$N\ K$
- All input values are integers.
- $1 \leq N \leq 2\times 10^5$
- $0 \leq K < 2^{18}$
Output
If no pair $(P,Q)$ satisfying the condition exists, print No.
If one exists, print Yes on the first line, $P$ on the second line, and $Q$ on the third line, in the following format.
Yes $P_1\ P_2\ \dots\ P_N$ $Q_1\ Q_2\ \dots\ Q_N$
If there are multiple pairs satisfying the condition, any of them will be accepted.
Sample
Sample 1
Input
4 2
Output
Yes 2 3 0 1 3 2 1 0
Let $\lor$ denote the binary operator of bitwise OR. For $P = (2,3,0,1), Q = (3,2,1,0)$, we have $\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$, so the condition is indeed satisfied.
Sample 2
Input
6 10
Output
No
No pair $(P,Q)$ satisfying the condition exists.
Sample 3
Input
9 12
Output
Yes 0 1 2 3 4 5 6 7 8 3 6 1 0 7 2 5 4 8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。