5я:

Разобъём все числа на 2 части — div K и mod K. Если поэкспериментировать, понятно, что в каждом сегменте — остатки будут последовательно увеличиваться, при этом одинакого для каждого сегмента, то есть комбинаций остатков всего K — (0,1,...,K-1), (1,2,...,K-1,0), ..., (K-1,0,1,...,K-2).

При этом, div K у нас тоже образуют последовательное увеличение, только с определённым остатком. Заведём дерево отрезков длины K, в листьях которого будем хранить div K для первого сегмента. Дерево будет реализовывать сумму по модулю (N/K) — у нас всего столько возможных div K. Ну и заведём число для остатка первого элемента первого сегмента.

Итого:

Операция 1: дерево не меняется, сдвигается вправо только модуль первого элемента сегмента. Операция 2: пускай двигаем на X (стороны не критичны — движение влево можно выразить через движение вправо). Тогда, ко всему дереву прибавляется X div K — мы двигаем сегменты целиком. Осталось додвигать X mod K. Тогда у нас модуль первого элемента сдвигается аналогично как в 1, только если он сдвигается с x1 на x2, то на циклическом отрезке [x1..x2-1] дерева прибавляем ещё 1.

После операций, объединяем числа, и получаем перестановку, которую мы сделали. Мой код.

жаль, что этот пост появился после контеста, а не до

Результаты.

You can find complete results here :http://www.hsin.hr/coci/results.php?contest=5