← 返回题目列表

Codeforces · 2032/B

B. 中位数

中文机器翻译题面 查看原题

给定一个数组 $$$a = [1, 2, \ldots, n]$$$(其中 $$$n$$$ 为奇数)和一个整数 $$$k$$$。

你的任务是选择一个奇数正整数 $$$m$$$ 并将 $$$a$$$ 拆分为 $$$m$$$ 子数组$$$^{\dagger}$$$ $$$b_1, b_2, \ldots, b_m$$$ ,这样:

- 数组 $$$a$$$ 的每个元素都属于一个子数组。
- 对于所有 $$$1 \le i \le m$$$,$$$|b_i|$$$ 是奇数,即每个子数组的长度是奇数。
- $$$\operatorname{median}([\operatorname{median}(b_1), \operatorname{median}(b_2), \ldots, \operatorname{median}(b_m)]) = k$$$,即所有子数组的中位数数组的中位数$$$^{\ddagger}$$$必须相等$$$k$$$。 $$$\operatorname{median}(c)$$$ 表示数组 $$$c$$$ 的中位数。

$$$^{\dagger}$$$长度为 $$$n$$$ 的数组 $$$a$$$ 的子数组是数组 $$$[a_l, a_{l + 1}, \ldots, a_r]$$$ 对于某些整数 $$$1 \le l \le r \le n$$$。

$$$^{\ddagger}$$$奇数长度数组的中位数是数组按非降序排序后的中间元素。例如:$$$\operatorname{median}([1,2,5,4,3]) = 3$$$、$$$\operatorname{median}([3,2,1]) = 2$$$、$$$\operatorname{median}([2,1,2,1,2,2,2]) = 2$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$($$$1 \le k \le n < 2 \cdot 10^5$$$,$$$n$$$ 为奇数)——数组 $$$a$$$ 的长度以及所有子数组中位数数组的所需中位数。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例:

- 如果没有合适的分区,则单行输出$$$-1$$$。
- 否则,在第一行中,输出一个奇数整数 $$$m$$$ ($$$1 \le m \le n$$$),并在第二行中,输出 $$$m$$$ 不同的整数 $$$p_1, p_2 , p_3 , \ldots, p_m$$$ ($$$1 = p_1 < p_2 < p_3 < \ldots < p_m \le n$$$) - 表示每个子数组的左边界。

详细来说,对于有效答案 $$$[p_1, p_2, \ldots, p_m]$$$:

- $$$b_1 = \left[ a_{p_1}, a_{p_1 + 1}, \ldots, a_{p_2 - 1} \right]$$$
- $$$b_2 = \left[ a_{p_2}, a_{p_2 + 1}, \ldots, a_{p_3 - 1} \right]$$$
- $$$\ldots$$$
- $$$b_m = \left[ a_{p_m}, a_{p_m + 1}, \ldots, a_n \right]$$$。

如果有多个解,则可以输出任意一个。

示例

输入 #1

4
1 1
3 2
3 3
15 8

输出 #1

1
1
3
1 2 3
-1
5
1 4 7 10 13

注意

在第一个测试用例中,给定分区具有 $$$m = 1$$$ 和 $$$b_1 = [1]$$$。显然 $$$\operatorname{median}([\operatorname{median}([1])]) = \operatorname{median}([1]) = 1$$$。

在第二个测试用例中,给定分区有 $$$m = 3$$$ 并且:

- $$$b_1 = [1]$$$
- $$$b_2 = [2]$$$
- $$$b_3 = [3]$$$

因此,$$$\operatorname{median}([\operatorname{median}([1]), \operatorname{median}([2]), \operatorname{median}([3])]) = \operatorname{median}([1, 2, 3]) = 2$$$。

在第三个测试用例中,$$$k = 3$$$ 没有有效分区。

在第四个测试用例中,给定分区有 $$$m = 5$$$ 并且:

- $$$b_1 = [1,2,3]$$$
- $$$b_2 = [4,5,6]$$$
- $$$b_3 = [7,8,9]$$$
- $$$b_4 = [10, 11, 12]$$$
- $$$b_5 = [13, 14, 15]$$$

因此, $$$\operatorname{median}([\operatorname{median}([1, 2, 3]), \operatorname{median}([4, 5, 6]), \operatorname{median}([7, 8, 9]), \operatorname{median}([10, 11, 12]), \operatorname{中位数}([13, 14, 15])]) = \operatorname{中位数}([2, 5, 8, 11, 14]) = 8$$$。