#P17621. [qaswed12 OI R1] Xor is Mex
[qaswed12 OI R1] Xor is Mex
背景
这是第一关。
题目描述
定义 为集合 中未出现的最小非负整数;对于一个长度为 的序列 , 等价于对序列中所有元素构成的集合求 。
符号与 符号的定义类似,求和变为求异或和,以及 符号表示两数按位异或。
qaswed12 给定了一个整数 ,你需要构造一个长度为 的非负整数序列 ,使得:
- 对于任意 ,有 。
- $\bigoplus\limits_{i=1}^t a_i = \operatorname{mex}(a_1, a_2, \dots, a_t)$。
若不存在满足条件的序列,输出 -1。
但是这个问题太简单了。
所以 qaswed12 对题目进行了改造,你需要构造一个非负整数序列 ,使得:
- ,且对于任意 ,有 。
- $\bigoplus\limits_{i=1}^{|A|} A_i = \operatorname{mex}(A_1, A_2, \dots, A_{|A|}) = t$。
其中 表示序列 的长度。
若不存在满足条件的序列,输出 -1。
注意:两问中的 是相同的。
qaswed12 想让你分别回答上述两个问题的答案。
输入格式
一行,一个正整数 。
输出格式
输出共两行:
- 第一行,包含 个整数,表示第一个问题构造的序列 。
若无解,输出-1。 - 第二行,输出一个整数 ,表示序列长度,
再输出 个数表示你构造的序列。若无解,输出-1。
3
0 1 2
3 0 1 2
提示
样例解释
对于第一问,满足 。
对于第二问,样例构造的序列长度为 ,且满足 $0 \oplus 1 \oplus 2 = \operatorname{mex}\{0,1,2\}=t$。
数据范围
本题所有测试点等分。
保证测试点编号的奇偶性与 的奇偶性相同。
| 测试点编号 | 特殊性质 | |
|---|---|---|
| 无 | ||
| ^ | ||
| 无 |
特殊性质 : 或 , 为正整数。
对于 的数据,满足 。
注意:请保证你的输出格式正确,否则可能会获得意料之外的评测结果。
评分标准
- 若你两问的答案均正确,你将获得该测试点的全部分数。
- 若你只有第一问的答案正确,你将获得 的分数。
- 若你只有第二问的答案正确,你将获得 的分数。
- 若你两问的答案全部错误,该测试点 分。