原案:admin

二分探索で解きます。
中央値をある値 \(X\) 以上にできるかどうかを判定します。
\(M\) 回の操作を行った後、棒の本数は \(N+M\) なので、最終状態において、長さ \(X\) 以上の棒が \(\frac{N+M+1}{2}\) 本あるようにできればよいです。
長さが \(2X-1\) 以上の棒を分割するのを可能な限り行い、それによって、長さが \(X\) 以上の棒が \(\frac{N+M+1}{2}\) 本以上なければ、中央値を \(X\) 以上にすることはできません。
また、そのような棒が \(\frac{N+M+1}{2}\) 本以上あるとし、短い方から \(\frac{N+M+1}{2}\) 本の棒の長さの合計を \(S\) とすると、それ以外の棒の長さは \(\sum_{i=1}^{N}{A_i}-S\) であり、それを \(\frac{N+M-1}{2}\) 本以下の棒にするためには、\(\frac{N+M-1}{2} \leq \sum_{i=1}^{N}{A_i}-S\) が必要です。
逆にこれらが満たされるとします。
長さが \(2X-1\) 以上の棒を分割する操作を可能な限り行って短い方から \(\frac{N+M+1}{2}\) 本はそこで操作をやめ、それ以外の棒に対しては操作を行えるだけ行っていくと、\(\frac{N+M+1}{2}+\sum_{i=1}^{N}{A_i}-S-N\) 回の操作を行うことになります。 これは、\(\frac{N+M+1}{2}+\frac{N+M-1}{2}-N=M\) 以上なので、操作をちょうど \(M\) 回行えることがわかります。

長さが \(2X-1\) 以上の棒を分割する操作を愚直にやろうとすると計算量が膨大になってしまいます。
長さが \(A_i\) の棒を分割していったときに生じうる棒の長さは \(\frac{A_i}{2^0},\frac{A_i}{2^1},\dots\) およびこれらに \(1\) を足したもののみであり、その種類数は \(O(\log \max(A))\) なので、大きい方からその長さの棒が何本あるかを調べていくことで、\(O(\log {\max(A)})\) でシミュレーションできます。

また、\(1\) 本の棒から始めて、長さが \(2X-1\) 以上の棒を分割する操作を可能な限り行ったとき、最終的な棒の長さの種類数は高々 \(3\) 種類なので、\(i=1,2,\dots,N\) に対して \(i\) 本目の棒を分割したとき、生じる棒の長さの種類は高々 \(O(N)\) 種類であり、これらのソートも \(O(N\log N)\) でできます。

全体の計算量は \(O(N(\log{ \max(A)})^2+N\log{N}\log{\max(A)})\) です。

追加問題

\(O(N\log{\max(A)})\) で解いてみましょう。