https://inamori.hateblo.jp/entry/20111130/p1

ガウス整数を使ってまじめに組んだら、35分で答えが出た。やれやれ。
実質的な計算は14分で終わっていたはずだが、そこで答えが出ない。最初はガベコレが働いているのかと思ったが、そこから延々と続いて35分。何が起こっていたのかいまだにわからない。

他の解がまったく思いつかないので、フォーラムを見た。そうやってやるんだ。そっち方面もちょっと考えたけど、出てこなかった。
これは、2つに分けてソートしてマージするので、本質的にはソートのO(NlogN)が計算量だと思うんだけど、PriorityQueueで速くならないのかな？明日やってみよう。