AOJ 2527 MLE

問題

MLE | Aizu Online Judge

解法

そのままソートすると時間計算量O(NlogN)でTLE、空間計算量O(N)でMLEする。
そこで、乱数列の各要素の上位16bitをキーにしたバケットソートみたいなことをする。
k 番目の値を調べる部分では、値が小さいキーから順に辿っていく。
バケットソートの結果だけではちょうど K 番目の値が見つからないので、その後境界になっているバケットの中身だけをvectorに入れて普通にソートする。
x0=0のときがコーナーケースで、生成される乱数列の値は全て0となるため0を出力するようにしておく。

詳細はソースコード参照