CF2032B Medians

给定一个数组 $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$，即所有子数组中位数组成的数组的中位数等于 $k$。$\operatorname{median}(c)$ 表示数组 $c$ 的中位数。 $^{\dagger}$ 数组 $a$ 长度为 $n$ 的子数组是 $[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, \ldots, p_m$（$1 = p_1 < p_2 < p_3 < \ldots < p_m \le n$），表示每个子数组的左端点。 具体来说，对于一个合法答案 $[p_1, p_2, \ldots, p_m]$： - $b_1 = [a_{p_1}, a_{p_1 + 1}, \ldots, a_{p_2 - 1}]$ - $b_2 = [a_{p_2}, a_{p_2 + 1}, \ldots, a_{p_3 - 1}]$ - $\ldots$ - $b_m = [a_{p_m}, a_{p_m + 1}, \ldots, a_n]$ 如果有多组解，输出任意一组均可。

在第一个测试用例中，给定的划分为 $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{median}([13, 14, 15])]) = \operatorname{median}([2, 5, 8, 11, 14]) = 8$。 由 ChatGPT 4.1 翻译