Rock Scissors Paper Train

解説

参加者の数は$2^{18} \approx 10^5$程度なので、最終的な列車の並びをマージソートと同じ要領で再帰を用いて構成すればよいです。マージソートと異なる点は、マージ操作を行う際、2つの配列を小さい順に1つの配列に組みなおす操作の代わりに、2つの配列の先頭にいる参加者の強さを比較してより強い方の配列に弱い方の配列を付け足す操作を行うことです。 時間計算量はマージソートと同様に$O(Nlog(N))$となり、今回の制約においては実行時間制限に間に合います。よって、この問題を解くことができました。