https://atcoder.jp/contests/agc006/submissions/20609588
- 中央値なので小中大(x-1, x, x+1)で並べる
- x, x, y の中央値は x
まず、一番上の段がxになるようにしないといけないので真ん中にxを置きたくなる(ぇ 次に、中央値なので x-1, x, x+1 と数字を並べてみる。残りの数字をどうするかだが実は適当で良く、とりあえず昇順に並べる。N段目の中央1つ隣のブロックが [大小中] となるため、N-1段目に [x, x, y] のような数列が出現する。x, x, y の中央値はxなので1段目がxになる。なお、xの値によってはN段目の中央1つ隣のブロックが [中大小] のようになることもあるが、結果的に同じなので大丈夫。
実装はdequeを使うと先頭と末尾にO(1)で挿入できて楽。
コーナーケースは x-1, x, x+1 と並べることから x=1 と x=2 * N - 1