Three MexAI (CI翻译)
Problem Statement
You are given non-negative integers $A, B, C$. Determine whether there exist sets of non-negative integers $X, Y$ satisfying the following three conditions, and if they exist, show one example.
- Each element of
$X, Y$is a non-negative integer at most$2026$. $\mathrm{mex}(X)=A, \mathrm{mex}(Y)=B$.- Define the set of non-negative integers
$Z$as$Z=\{x\oplus y\mid x\in X, y \in Y\}$. Then,$\mathrm{mex}(Z)=C$. Here,$\oplus$denotes the bitwise$\mathrm{XOR}$operation.
What is $\mathrm{mex}(S)$? For a finite set $S$ of non-negative integers, $\mathrm{mex}(S)$ is defined as the smallest non-negative integer $s$ satisfying $s\notin S$.
What is the bitwise $\mathrm{XOR}$ operation? The bitwise $\mathrm{XOR}$ of non-negative integers $x$ and $y$, $x \oplus y$, is defined as follows. When $x \oplus y$ is written in binary, the digit in the $2^k$ ($k \geq 0$) place is $1$ if exactly one of the digits in the $2^k$ place of $x$ and $y$ written in binary is $1$, and $0$ otherwise. For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).
Solve $T$ test cases per input file.
Constraints
$1 \leq T \leq 10$$0 \leq A \leq 1000$$0 \leq B \leq 1000$$0 \leq C \leq 1000$- All input values are integers.
Input
The input is given from Standard Input in the following format. Here, $\mathrm{case}_i$ ($1 \leq i \leq T$) denotes the $i$-th test case.
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_TEach test case is given in the following format:
A B COutput
Output the answers in the order $\mathrm{case}_1, \mathrm{case}_2, \cdots, \mathrm{case}_T$. For each test case, output as follows.
- If there do not exist sets of non-negative integers
$X, Y$satisfying the conditions, outputNofollowed by a newline. - If there exist sets of non-negative integers
$X, Y$satisfying the conditions, output one example in the following format. Let$N, M$be the numbers of elements of$X, Y$, respectively, let$X_i$be the$i$-th element ($1 \leq i \leq N$) of$X$, and let$Y_j$be the$j$-th element ($1 \leq j \leq M$) of$Y$. Here,$X_1, X_2, \cdots, X_N$must be pairwise distinct. Also,$Y_1, Y_2, \cdots, Y_M$must be pairwise distinct. If there are multiple pairs of sets of non-negative integers$X, Y$satisfying the conditions, any of them will be judged as correct.
Yes
N X_1 X_2 \cdots X_N
M Y_1 Y_2 \cdots Y_M{"titleZh":"三个 Mex","bodyZh":"## 题目描述\n\n给定非负整数 $A, B, C$。请判断是否存在满足以下三个条件的非负整数集合 X、Y；如果存在，请给出一个例子。\n\n- X、Y 中的每个元素都是不超过 $2026$ 的非负整数。\n- $\mathrm{mex}(X)=A, \mathrm{mex}(Y)=B$。\n- 将非负整数集合 $Z$ 定义为 $Z=\\{x\\oplus y\\mid x\\in X, y \\in Y\\}$。此时，$\mathrm{mex}(Z)=C$。其中，$\oplus$ 表示按位 $\mathrm{XOR}$ 运算。\n\n什么是 $\mathrm{mex}(S)$？对于非负整数的有限集合 $S$，$\mathrm{mex}(S)$ 定义为满足 $s\\notin S$ 的最小非负整数 $s$。\n\n什么是按位 $\mathrm{XOR}$ 运算？非负整数 $x$ 和 $y$ 的按位 $\mathrm{XOR}$ 运算 $x \\oplus y$ 定义如下。将 $x \\oplus y$ 写成二进制时，如果 $x$ 和 $y$ 的二进制表示在 $2^k$ ($k \\geq 0$) 位上的数字中恰有一个为 $1$，则该位为 $1$，否则为 $0$。例如，$3 \\oplus 5 = 6$（二进制表示为：$011 \\oplus 101 = 110$）。\n\n每个输入文件包含 $T$ 个测试用例。\n\n## 约束条件\n\n- $1 \\leq T \\leq 10$\n- $0 \\leq A \\leq 1000$\n- $0 \\leq B \\leq 1000$\n- $0 \\leq C \\leq 1000$\n- 输入的所有值均为整数。\n\n## 输入格式\n\n输入从标准输入读入，格式如下。其中，$\\mathrm{case}_i$（$1 \\leq i \\leq T$）表示第 $i$ 个测试用例。\n\n\nT\n\\mathrm{case}_1\n\\mathrm{case}_2\n\\vdots\n\\mathrm{case}_T\n`\n\n每个测试用例的格式如下：\n\n`\nA B C\n`\n\n## 输出格式\n\n按照 $\\mathrm{case}_1, \\mathrm{case}_2, \\cdots, \\mathrm{case}_T$ 的顺序输出答案。每个测试用例按以下格式输出。\n\n- 如果不存在满足条件的非负整数集合 X、Y，输出 No 并换行。\n- 如果存在满足条件的非负整数集合 X、Y，按照以下格式输出一个例子。设 $N, M$ 分别为集合 $X, Y$ 中元素的个数，设 $X_i$ 为 $X$ 的第 $i$ 个元素（$1 \\leq i \\leq N$），$Y_j$ 为 $Y$ 的第 $j$ 个元素（$1 \\leq j \\leq M$）。其中，$X_1, X_2, \\cdots, X_N$ 必须两两不同，$Y_1, Y_2, \\cdots, Y_M$ 也必须两两不同。如果存在多组满足条件的非负整数集合 X、Y，输出其中任意一组均可被判定为正确。\n\n`\nYes\nN X_1 X_2 \\cdots X_N\nM Y_1 Y_2 \\cdots Y_M\n
样例
4
2 3 6
1 1 0
0 0 1
0 0 0
Yes
3 0 1 3
4 0 1 2 4
No
Yes
1 1
1 1
Yes
0
3 2026 10 4
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。