33OJ
登录 注册

#P17623. [qaswed12 OI R1] Xor in Mex

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

[qaswed12 OI R1] Xor in Mex

背景

还有第二关?

题目描述

qaswed12 想让你构造一个长度为 nn 的整数序列 aa,使得:

  • 对于任意 1≤i≤n1 \le i \le n,有 0≤ai≤n.0 \le a_i \le n.
  • $k=\bigoplus\limits_{l=1}^{n}\bigoplus\limits_{r=l}^{n}\operatorname{mex}(l,r)$.

其中 kk 是给定的值。

mex⁡(l,r)\operatorname{mex}(l,r) 定义为在 al,al+1,...,ara_l,a_{l+1},...,a_r 中未出现的最小非负整数。

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

若有多个满足条件的方案,输出任意一个即可。无解输出 -1。

输入格式

一行两个整数 n,kn,k。

输出格式

输出一行表示你构造的序列 aa,用空格分开,无解请输出 -1。

3 3
1 0 1
13 1
1 1 4 5 1 4 1 9 1 9 8 1 0
4 9
-1

提示

样例解释 #1

$\begin{aligned} & \bigoplus\limits_{l=1}^{3}\bigoplus\limits_{r=l}^{3}\operatorname{mex}(l,r) \\ = & \operatorname{mex}(1,1) \oplus \operatorname{mex}(1,2) \oplus \operatorname{mex}(1,3) \oplus \operatorname{mex}(2,2) \oplus \operatorname{mex}(2,3) \oplus \operatorname{mex}(3,3) \\ = & \,0 \oplus 2 \oplus 2 \oplus 1 \oplus 2 \oplus 0 \\ = & \,3 \end{aligned}$

数据范围

本题开启捆绑测试。

子任务编号 nn kk 特殊性质 得分
11 ≤8\le 8 ≤16\le 16 无 44
22 ≤1000\le 1000 ≤3\le 3 nn 为偶数 1212
33 ^ 无 1616
44 ≤105\le 10^5 =0=0 ^ 44
55 ^ ≤⌈n2⌉\le \lceil \frac{n}{2} \rceil 1212
66 =n=n 1616
77 ≤5×105\le 5 \times 10^5 ≤109\le 10^9 nn 为偶数
88 ^ 无 2020

对于 100%100\% 的数据,满足 1≤n≤5×1051\le n\le 5 \times 10^5,0≤k≤1090\le k\le 10^{9}。