33OJ
登录 注册

#P17621. [qaswed12 OI R1] Xor is Mex

    ID: 20212 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及+/提高− 上传者: 标签>Special JudgeO2优化构造Ad-hoc分类讨论

[qaswed12 OI R1] Xor is Mex

背景

这是第一关。

题目描述

定义 mex⁡{S}\operatorname{mex}\{S\} 为集合 SS 中未出现的最小非负整数;对于一个长度为 nn 的序列 AA,mex⁡(A1,A2,…,An)\operatorname{mex}(A_1, A_2, \dots, A_n) 等价于对序列中所有元素构成的集合求 mex⁡\operatorname{mex}。

⨁\bigoplus 符号与 ∑\sum 符号的定义类似,求和变为求异或和,以及 ⊕\oplus 符号表示两数按位异或。


qaswed12 给定了一个整数 tt,你需要构造一个长度为 tt 的非负整数序列 aa,使得:

  • 对于任意 1≤i≤t1 \le i \le t,有 0≤ai≤t0 \le a_i \le t。
  • $\bigoplus\limits_{i=1}^t a_i = \operatorname{mex}(a_1, a_2, \dots, a_t)$。

若不存在满足条件的序列,输出 -1。

但是这个问题太简单了。

所以 qaswed12 对题目进行了改造,你需要构造一个非负整数序列 AA,使得:

  • 1≤∣A∣<1061 \le |A| < 10^6,且对于任意 1≤i≤∣A∣1 \le i \le |A|,有 0≤Ai<1060 \le A_i < 10^6。
  • $\bigoplus\limits_{i=1}^{|A|} A_i = \operatorname{mex}(A_1, A_2, \dots, A_{|A|}) = t$。

其中 ∣A∣|A| 表示序列 AA 的长度。

若不存在满足条件的序列,输出 -1。

注意:两问中的 t\mathbf t 是相同的。

qaswed12 想让你分别回答上述两个问题的答案。

输入格式

一行,一个正整数 tt。

输出格式

输出共两行:

  • 第一行,包含 tt 个整数,表示第一个问题构造的序列 AA。
    若无解,输出 -1。
  • 第二行,输出一个整数 mm ,表示序列长度,
    再输出 mm 个数表示你构造的序列。若无解,输出 -1。
3
0 1 2
3 0 1 2

提示

样例解释

对于第一问,满足 0⊕1⊕2=mex⁡{0,1,2}0 \oplus 1 \oplus 2=\operatorname{mex}\{0,1,2\}。

对于第二问,样例构造的序列长度为 m=3m=3,且满足 $0 \oplus 1 \oplus 2 = \operatorname{mex}\{0,1,2\}=t$。

数据范围

本题所有测试点等分。

保证测试点编号的奇偶性与 tt 的奇偶性相同。

测试点编号 t≤t \le 特殊性质
1∼21 \sim 2 66 无
3∼63 \sim 6 10310^3 ^
7∼127 \sim 12 10510^5
13∼1413 \sim 14 10610^6 A\text A
15∼2015 \sim 20 无

特殊性质 A\text A:t=2at=2^a 或 t=2a−1t=2^a-1,aa 为正整数。

对于 100%100\% 的数据,满足 1≤t≤1061 \le t \le 10^6。

注意:请保证你的输出格式正确,否则可能会获得意料之外的评测结果。

评分标准

  • 若你两问的答案均正确,你将获得该测试点的全部分数。
  • 若你只有第一问的答案正确,你将获得 40%40\% 的分数。
  • 若你只有第二问的答案正确,你将获得 60%60\% 的分数。
  • 若你两问的答案全部错误,该测试点 00 分。