F - Half and Median 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 550 点

問題文

N 本の棒があり、i 本目の棒の長さは A_i です。
以下の操作を M 回行います。

  • 長さが 2 以上の棒を 1 本選び、この棒の長さを l と置く。この棒を、長さが \left\lfloor\frac{l}{2}\right\rfloor と \left\lceil\frac{l}{2}\right\rceil の 2 本の棒に分割する。

制約から、操作を M 回行うことは可能であることが証明できます。
M 回の操作後、N+M 本の棒が残りますが、これらの棒の長さの中央値としてありうる値の最大値を求めてください。

1 つの入力につき、T 個のテストケースを解いてください。

中央値とは N が偶数であるとき、N+1 個の数の中央値とは、それらを昇順に並べたときに (1+\frac{N}{2}) 番目の値です。
例えば、(1,3,4,5,8) の中央値は 4、(2,2,2) の中央値は 2 です。
本問題において、長さの中央値を考える棒の本数は制約から常に奇数であることに注意してください。

制約

  • 1 \leq T \leq 10^5
  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq M \leq \sum_{i=1}^{N}{A_i} - N
  • N+M は奇数
  • 全てのテストケースにおける N の総和は 10^5 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
case_1
case_2
\vdots
case_T

各ケースは以下の形式で与えられる。

N M  
A_1 A_2 \ldots A_N

出力

答えを合計 T 行で出力せよ。 t 行目には、t 番目のテストケースの答えを出力せよ。

入力例 1

3
5 2
14 2 5 19 1
10 1
10 6 7 6 2 20 9 16 3 3
4 1
444 444 44 444

出力例 1

7
7
444

1 つ目のテストケースでは、1 回目の操作で長さ 14 の棒を選ぶとその棒は長さ 7 の棒 2 本に分割され、6 本の棒の長さは 7,7,2,5,19,1 になります。 2 回目の操作で長さ 19 の棒を選ぶとその棒は長さ 9,10 の棒 2 本に分割され、7 本の棒の長さは 7,7,2,5,9,10,1 になります。 このとき、棒の長さの中央値は 7 になります。

Score : 550 points

Problem Statement

There are N sticks, and the length of the i-th stick is A_i.
You will perform the following operation M times:

  • Choose one stick of length at least 2, and let l be the length of this stick. Divide this stick into two sticks of lengths \left\lfloor\frac{l}{2}\right\rfloor and \left\lceil\frac{l}{2}\right\rceil.

From the constraints, it can be proved that it is possible to perform the operation M times.
After M operations, N+M sticks will remain. Find the maximum possible value of the median of the lengths of these sticks.

Solve T test cases per input.

What is the median? When N is even, the median of N+1 numbers is the (1+\frac{N}{2})-th value when they are sorted in ascending order.
For example, the median of (1,3,4,5,8) is 4, and the median of (2,2,2) is 2.
Note that in this problem, from the constraints, the number of sticks to consider for the median of lengths is always odd.

Constraints

  • 1 \leq T \leq 10^5
  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq M \leq \sum_{i=1}^{N}{A_i} - N
  • N+M is odd.
  • The sum of N over all test cases is at most 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is given in the following format:

N M  
A_1 A_2 \ldots A_N

Output

Output the answers in T lines in total. The t-th line should contain the answer for the t-th test case.

Sample Input 1

3
5 2
14 2 5 19 1
10 1
10 6 7 6 2 20 9 16 3 3
4 1
444 444 44 444

Sample Output 1

7
7
444

In the first test case, if you choose the stick of length 14 in the first operation, it is divided into two sticks of length 7, and now you have six sticks of lengths 7,7,2,5,19,1. If you choose the stick of length 19 in the second operation, it is divided into two sticks of lengths 9,10, and now you have seven sticks of lengths 7,7,2,5,9,10,1. In this case, the median of the stick lengths is 7.