|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 16-3. Восстановление перестановки
(Разбор)
Заведем массив А из 0 и 1, в котором А[i] равно 0, если мы еще не поставили число i в перестановку, и 1 - иначе. Обрабатываем таблицу инверсий справа налево. На каждом шаге i мы на i-тое место в будущей перестановке ставим индекс φ[i]+1 нуля в массиве А, считая справа налево, после этого изменяем ноль на единицу.