AT_arc231_b.Three Mex

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given non-negative integers A,B,CA, B, C. Determine whether there exist sets of non-negative integers X,YX, Y satisfying the following three conditions, and if they exist, show one example.

  • Each element of X,YX, Y is a non-negative integer at most 20262026.
  • mex(X)=A,mex(Y)=B\mathrm{mex}(X)=A, \mathrm{mex}(Y)=B.
  • Define the set of non-negative integers ZZ as Z=x⊕y∣x∈X,y∈YZ={x\oplus y\mid x\in X, y \in Y}. Then, mex(Z)=C\mathrm{mex}(Z)=C. Here, ⊕\oplus denotes the bitwise XOR\mathrm{XOR} operation.

What is mex(S)\mathrm{mex}(S)? For a finite set SS of non-negative integers, mex(S)\mathrm{mex}(S) is defined as the smallest non-negative integer ss satisfying s∉Ss\notin S. What is the bitwise XOR\mathrm{XOR} operation?

The bitwise XOR\mathrm{XOR} of non-negative integers xx and yy, x⊕yx \oplus y, is defined as follows.

  • When x⊕yx \oplus y is written in binary, the digit in the 2k2^k (k≥0k \geq 0) place is 11 if exactly one of the digits in the 2k2^k place of xx and yy written in binary is 11, and 00 otherwise.

For example, 3⊕5=63 \oplus 5 = 6 (in binary: 011⊕101=110011 \oplus 101 = 110).

Solve TT test cases per input file.

给定非负整数 A,B,CA, B, C。请判断是否存在满足以下三个条件的非负整数集合 X,YX, Y;若存在,请给出一组示例。

  • XX 与 YY 中的每个元素均为不超过 20262026 的非负整数;
  • mex(X)=A, mex(Y)=B\mathrm{mex}(X)=A,\ \mathrm{mex}(Y)=B;
  • 定义非负整数集合 Z={x⊕y∣x∈X, y∈Y}Z = \{x \oplus y \mid x \in X,\ y \in Y\},则需满足 mex(Z)=C\mathrm{mex}(Z) = C。其中 ⊕\oplus 表示按位异或(bitwise XOR)运算。

什么是 mex(S)\mathrm{mex}(S)?
对于一个有限的非负整数集合 SS,mex(S)\mathrm{mex}(S) 定义为不包含于 SS 中的最小非负整数 ss。

什么是按位异或(bitwise XOR)运算?
非负整数 xx 与 yy 的按位异或 x⊕yx \oplus y 定义如下:

  • 将 x⊕yx \oplus y 写成二进制形式时,其 2k2^k 位(k≥0k \geq 0)上的数字为 11,当且仅当 xx 与 yy 的二进制表示在 2k2^k 位上恰好有一个为 11;否则该位为 00。

例如:3⊕5=63 \oplus 5 = 6(二进制:011⊕101=110011 \oplus 101 = 110)。

每组输入文件需解决 TT 个测试用例。

输入格式

The input is given from Standard Input in the following format. Here, casei\mathrm{case}_i (1≤i≤T1 \leq i \leq T) denotes the ii-th test case.

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

Each test case is given in the following format:

AA BB CC

输入从标准输入中按以下格式给出。其中,casei\mathrm{case}_i(1≤i≤T1 \leq i \leq T)表示第 ii 个测试用例。

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

每个测试用例按以下格式给出:

AA BB CC

输出格式

Output the answers in the order case1,case2,⋯ ,caseT\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,YX, Y satisfying the conditions, output No followed by a newline.
  • If there exist sets of non-negative integers X,YX, Y satisfying the conditions, output one example in the following format. Let N,MN, M be the numbers of elements of X,YX, Y, respectively, let XiX_i be the ii-th element (1≤i≤N1 \leq i \leq N) of XX, and let YjY_j be the jj-th element (1≤j≤M1 \leq j \leq M) of YY. Here, X1,X2,⋯ ,XNX_1, X_2, \cdots, X_N must be pairwise distinct. Also, Y1,Y2,⋯ ,YMY_1, Y_2, \cdots, Y_M must be pairwise distinct. If there are multiple pairs of sets of non-negative integers X,YX, Y satisfying the conditions, any of them will be judged as correct.

Yes
NN X1X_1 X2X_2 ⋯\cdots XNX_N
MM Y1Y_1 Y2Y_2 ⋯\cdots YMY_M

按 case1,case2,⋯ ,caseT\mathrm{case}_1, \mathrm{case}_2, \cdots, \mathrm{case}_T 的顺序输出答案。对于每个测试用例,按如下方式输出:

  • 若不存在满足条件的非负整数集合 X,YX, Y,则输出 No 并换行。
  • 若存在满足条件的非负整数集合 X,YX, Y,则按以下格式输出其中一组解。设 N,MN, M 分别为集合 X,YX, Y 的元素个数,XiX_i 表示 XX 的第 ii 个元素(1≤i≤N1 \leq i \leq N),YjY_j 表示 YY 的第 jj 个元素(1≤j≤M1 \leq j \leq M)。其中,X1,X2,⋯ ,XNX_1, X_2, \cdots, X_N 必须两两互异;同样,Y1,Y2,⋯ ,YMY_1, Y_2, \cdots, Y_M 也必须两两互异。若存在多组满足条件的非负整数集合 X,YX, Y,输出任意一组均视为正确。

Yes
NN X1X_1 X2X_2 ⋯\cdots XNX_N
MM Y1Y_1 Y2Y_2 ⋯\cdots YMY_M

输入输出样例

  • 输入#1

    4
    2 3 6
    1 1 0
    0 0 1
    0 0 0

    输出#1

    Yes
    3 0 1 3
    4 0 1 2 4
    No
    Yes
    1 1
    1 1
    Yes
    0
    3 2026 10 4

说明/提示

Sample 1 Explanation:

  • For the first test case, since X=0,1,3,Y=0,1,2,4X = { 0, 1, 3 }, Y = { 0, 1, 2, 4 }, we have Z=0,1,2,3,4,5,7Z = {0, 1, 2, 3, 4, 5, 7 }, which satisfies mex(X)=2,mex(Y)=3,mex(Z)=6\mathrm{mex}(X) = 2, \mathrm{mex}(Y) = 3, \mathrm{mex}(Z) = 6.
  • For the second test case, there do not exist sets of non-negative integers X,YX, Y satisfying the conditions.
  • For the fourth test case, X,YX, Y may be empty sets.

Constraints

  • 1≤T≤101 \leq T \leq 10
  • 0≤A≤10000 \leq A \leq 1000
  • 0≤B≤10000 \leq B \leq 1000
  • 0≤C≤10000 \leq C \leq 1000
  • All input values are integers.

样例 1 解释:

  • 对于第一个测试用例,由于 X={0,1,3}, Y={0,1,2,4}X = \{ 0, 1, 3 \},\ Y = \{ 0, 1, 2, 4 \},我们有 Z={0,1,2,3,4,5,7}Z = \{0, 1, 2, 3, 4, 5, 7 \},满足 mex(X)=2, mex(Y)=3, mex(Z)=6\mathrm{mex}(X) = 2,\ \mathrm{mex}(Y) = 3,\ \mathrm{mex}(Z) = 6。
  • 对于第二个测试用例,不存在满足条件的非负整数集合 X, YX,\ Y。
  • 对于第四个测试用例,X, YX,\ Y 可以是空集。

约束条件

  • 1≤T≤101 \leq T \leq 10
  • 0≤A≤10000 \leq A \leq 1000
  • 0≤B≤10000 \leq B \leq 1000
  • 0≤C≤10000 \leq C \leq 1000
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页