Medians
Contest: Codeforces Round 983 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, greedy, implementation, math

You are given an array $$$a = [1, 2, \ldots, n]$$$, where $$$n$$$ is odd, and an integer $$$k$$$.

Your task is to choose an odd positive integer $$$m$$$ and to split $$$a$$$ into $$$m$$$ subarrays$$$^{\dagger}$$$ $$$b_1, b_2, \ldots, b_m$$$ such that:

- Each element of the array $$$a$$$ belongs to exactly one subarray.
- For all $$$1 \le i \le m$$$, $$$|b_i|$$$ is odd, i.e., the length of each subarray is odd.
- $$$\operatorname{median}([\operatorname{median}(b_1), \operatorname{median}(b_2), \ldots, \operatorname{median}(b_m)]) = k$$$, i.e., the median$$$^{\ddagger}$$$ of the array of medians of all subarrays must equal $$$k$$$. $$$\operatorname{median}(c)$$$ denotes the median of the array $$$c$$$.

$$$^{\dagger}$$$A subarray of the array $$$a$$$ of length $$$n$$$ is the array $$$[a_l, a_{l + 1}, \ldots, a_r]$$$ for some integers $$$1 \le l \le r \le n$$$.

$$$^{\ddagger}$$$A median of the array of odd length is the middle element after the array is sorted in non-decreasing order. For example: $$$\operatorname{median}([1,2,5,4,3]) = 3$$$, $$$\operatorname{median}([3,2,1]) = 2$$$, $$$\operatorname{median}([2,1,2,1,2,2,2]) = 2$$$.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n < 2 \cdot 10^5$$$, $$$n$$$ is odd) — the length of array $$$a$$$ and the desired median of the array of medians of all subarrays.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case:

- If there is no suitable partition, output $$$-1$$$ in a single line.
- Otherwise, in the first line, output an odd integer $$$m$$$ ($$$1 \le m \le n$$$), and in the second line, output $$$m$$$ distinct integers $$$p_1, p_2 , p_3 , \ldots, p_m$$$ ($$$1 = p_1 < p_2 < p_3 < \ldots < p_m \le n$$$) — denoting the left borders of each subarray.

In detail, for a valid answer $$$[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]$$$.

If there are multiple solutions, you can output any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the given partition has $$$m = 1$$$ and $$$b_1 = [1]$$$. It is obvious that $$$\operatorname{median}([\operatorname{median}([1])]) = \operatorname{median}([1]) = 1$$$.

In the second test case, the given partition has $$$m = 3$$$ and:

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

Therefore, $$$\operatorname{median}([\operatorname{median}([1]), \operatorname{median}([2]), \operatorname{median}([3])]) = \operatorname{median}([1, 2, 3]) = 2$$$.

In the third test case, there is no valid partition for $$$k = 3$$$.

In the fourth test case, the given partition has $$$m = 5$$$ and:

- $$$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]$$$

Therefore, $$$\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$$$.

Example input:
4
1 1
3 2
3 3
15 8

Example output:
1
1
3
1 2 3
-1
5
1 4 7 10 13

Editorial:
For $$$n = 1$$$ (and $$$k = 1$$$ as well), the obvious answer would be not partitioning anything, i.e., partition with 1 subarray being itself.
For $$$n > 1$$$, we see that $$$k = 1$$$ and $$$k = n$$$ cannot yield a satisfactory construction. Proof is as follows:
• $$$m = 1$$$ will yield $$$ans = \lfloor \frac{n+1}{2} \rfloor$$$, which will never be equal to $$$1$$$ or $$$n$$$ when $$$n \ge 3$$$.
• If $$$m > 1$$$, considering the case of $$$k = 1$$$, we see that $$$\operatorname{median}(b_i) = 1$$$ iff $$$i \ge 2$$$, and since the original array $$$a$$$ is an increasingly-sorted permutation, we can conclude that $$$\operatorname{median}(b_1) < 1$$$. This is not possible.
• Similarly, $$$k = n$$$ also doesn't work with $$$m > 1$$$, as it'll require $$$\operatorname{median}(b_m) > n$$$.
Apart from these cases, any other $$$k$$$ can yield an answer with $$$m = 3$$$  — a prefix subarray $$$b_1$$$, a middle subarray $$$b_2$$$ containing $$$k$$$ ($$$b_2$$$ will be centered at $$$k$$$, of course), and a suffix subarray $$$b_3$$$. This way, the answer will be $$$\operatorname{median}(b_2) = k$$$.
The length of $$$b_2$$$ can be either $$$1$$$ or $$$3$$$, depending on the parity of $$$k$$$ (so that $$$b_1$$$ and $$$b_3$$$ could have odd lengths). In detail: $$$b_2$$$ will have length $$$1$$$ (i.e., $$$[k]$$$) if $$$k$$$ is an even integer, and length $$$3$$$ (i.e., $$$[k-1, k, k+1]$$$) if $$$k$$$ is an odd integer.
Time complexity: $$$\mathcal{O}(1)$$$.