No.366

まず座標圧縮して $1 \leq a_i \leq N$ となるようにする. そうすると, ソート後は $i$ 番目に $i$ の数値がくるようになる.

YURAFUNA君は $i$ 番目と $i + K$ 番目しか入れ替えられないので, $K$ で割った余りが同じ位置のもの同士しか入れ替えられない. よって, $K$ で割った余りの位置に $K$ で割った余りが同じ数値以外が入っている場合はソートできない.

あとは $K$ で割った余りが同じ位置同士でバブルソートの要領で一番小さい数値を前に寄せていけばいい.