AT_arc231_b.Three Mex
提高+/省选-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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.
- mex(X)=A,mex(Y)=B.
- Define the set of non-negative integers Z as Z=x⊕y∣x∈X,y∈Y. Then, mex(Z)=C. Here, ⊕ denotes the bitwise XOR operation.
What is mex(S)? For a finite set S of non-negative integers, mex(S) is defined as the smallest non-negative integer s satisfying s∈/S. What is the bitwise XOR operation?
The bitwise XOR of non-negative integers x and y, x⊕y, is defined as follows.
- When x⊕y is written in binary, the digit in the 2k (k≥0) place is 1 if exactly one of the digits in the 2k place of x and y written in binary is 1, and 0 otherwise.
For example, 3⊕5=6 (in binary: 011⊕101=110).
Solve T test cases per input file.
给定非负整数 A,B,C。请判断是否存在满足以下三个条件的非负整数集合 X,Y;若存在,请给出一组示例。
- X 与 Y 中的每个元素均为不超过 2026 的非负整数;
- mex(X)=A, mex(Y)=B;
- 定义非负整数集合 Z={x⊕y∣x∈X, y∈Y},则需满足 mex(Z)=C。其中 ⊕ 表示按位异或(bitwise XOR)运算。
什么是 mex(S)?
对于一个有限的非负整数集合 S,mex(S) 定义为不包含于 S 中的最小非负整数 s。
什么是按位异或(bitwise XOR)运算?
非负整数 x 与 y 的按位异或 x⊕y 定义如下:
- 将 x⊕y 写成二进制形式时,其 2k 位(k≥0)上的数字为 1,当且仅当 x 与 y 的二进制表示在 2k 位上恰好有一个为 1;否则该位为 0。
例如:3⊕5=6(二进制:011⊕101=110)。
每组输入文件需解决 T 个测试用例。
输入格式
The input is given from Standard Input in the following format. Here, casei (1≤i≤T) denotes the i-th test case.
T
case1
case2
⋮
caseT
Each test case is given in the following format:
A B C
输入从标准输入中按以下格式给出。其中,casei(1≤i≤T)表示第 i 个测试用例。
T
case1
case2
⋮
caseT
每个测试用例按以下格式给出:
A B C
输出格式
Output the answers in the order case1,case2,⋯,caseT. For each test case, output as follows.
- If there do not exist sets of non-negative integers X,Y satisfying the conditions, output
Nofollowed 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 Xi be the i-th element (1≤i≤N) of X, and let Yj be the j-th element (1≤j≤M) of Y. Here, X1,X2,⋯,XN must be pairwise distinct. Also, Y1,Y2,⋯,YM 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 X1 X2 ⋯ XN
M Y1 Y2 ⋯ YM
按 case1,case2,⋯,caseT 的顺序输出答案。对于每个测试用例,按如下方式输出:
- 若不存在满足条件的非负整数集合 X,Y,则输出
No并换行。 - 若存在满足条件的非负整数集合 X,Y,则按以下格式输出其中一组解。设 N,M 分别为集合 X,Y 的元素个数,Xi 表示 X 的第 i 个元素(1≤i≤N),Yj 表示 Y 的第 j 个元素(1≤j≤M)。其中,X1,X2,⋯,XN 必须两两互异;同样,Y1,Y2,⋯,YM 也必须两两互异。若存在多组满足条件的非负整数集合 X,Y,输出任意一组均视为正确。
Yes
N X1 X2 ⋯ XN
M Y1 Y2 ⋯ YM
输入输出样例
输入#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,4, we have Z=0,1,2,3,4,5,7, which satisfies mex(X)=2,mex(Y)=3,mex(Z)=6.
- For the second test case, there do not exist sets of non-negative integers X,Y satisfying the conditions.
- For the fourth test case, X,Y may be empty sets.
Constraints
- 1≤T≤10
- 0≤A≤1000
- 0≤B≤1000
- 0≤C≤1000
- All input values are integers.
样例 1 解释:
- 对于第一个测试用例,由于 X={0,1,3}, Y={0,1,2,4},我们有 Z={0,1,2,3,4,5,7},满足 mex(X)=2, mex(Y)=3, mex(Z)=6。
- 对于第二个测试用例,不存在满足条件的非负整数集合 X, Y。
- 对于第四个测试用例,X, Y 可以是空集。
约束条件
- 1≤T≤10
- 0≤A≤1000
- 0≤B≤1000
- 0≤C≤1000
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?