Codeforces Round 983 (Div. 2) |
---|
Finished |
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:
$$$^{\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$$$.
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$$$.
For each test case:
In detail, for a valid answer $$$[p_1, p_2, \ldots, p_m]$$$:
If there are multiple solutions, you can output any of them.
41 13 23 315 8
1 1 3 1 2 3 -1 5 1 4 7 10 13
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:
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:
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$$$.
Name |
---|