И не будет, все уже спать пошли. Надеюсь, что завтра хоть увидим

Вот Результаты -> http://neerc.ifmo.ru/school/io/archive/20130318/standings-20130318-individual.html

The tests&checkers are not published yet

Ну вот лично я решал так:

Будем для каждого a[i] считать число элементов таких, что a[i] < a[j] и i > j, то есть инверсии по сути. Это можно сделать деревом Фенвика, например. Затем заметим, что после каждого прохода Гарри у каждого a[i] это число либо уменьшается на 1, если больше 0, либо остается 0. То есть за k ходов все эти значения уменьшатся на k, если больше k, либо станут = 0.

Теперь нам нужно по этим данным восстановить исходную перестановку. Можно это сделать по-разному, например деревом отрезков для суммы на отрезке, но так как ограничения позволяют вполне — можно схалявить и написать того же фенвика и бинпоиск. Просто мы будем расставлять элементы в порядке увеличения их значения. То есть сначала мы найдем позицию для 1, потом для 2, 3 и так далее... Просто бинпоиском ищем нашу позицию и фенвиком узнаем — сколько позиций до нашей не занято — там однозначно будут стоять бОльшие числа.

Мой код

Сначала поймем — когда ответ IMPOSSIBLE. По очевидным причинам так происходит, когда у нас больше одной вершины со степенью 1. Единственное исключение — случай, когда у нас всего 2 вершины — такого, кстати, в тестах не было почему-то.

Теперь, собственно, само решение:

Известно, что gcd(x, x + 1) = 1. Используем это. Нам нужно обойти наш граф так, чтобы у каждой вершины (кроме начальной) были ребра с числами x и x + 1. Это сделать очень просто — идем dfs-ом из вершины со степенью 1, если такая есть, иначе из любой. И просто проставляем цифры по порядку от 1 до m. Это всегда будет верно, потому что, если степень вершины > 1, то мы из неё сможем перейти дальше, а если мы пришли в неё по ребру x, то куда-то из неё мы пойдем по ребру x + 1.

Сортируем массив. Понятно, что теперь минимальная разница будет между соседними элементами. Проходим по нему и пихаем в дерево разницы между соседними элементами, сравнивая как сказано в условии. Теперь просто на каждой из n итераций берём и удаляем лучшие 2 элемента из дерева. Пусть из {a, b, c, d} мы выбрали (b, c). Тогда удаляем из дерева a-b, b-c и c-d (учитывая крайние случаи), вставляем a-d. Только нужно ещё поддерживать для каждого элемента указатели к соседним неудалённым элементам.

О! У задач есть naming collisions, например 65D - Гарри Поттер и Распределяющая Шляпа.

Добавил в тренировки 2012-2013 Цикл интернет-олимпиад. Восьмая личная олимпиада (18 марта 2013 года), финальный тур ИОИП (17 марта 2013 года). Лучи уважения авторам — контест распарсился легко и непринужденно.

Простите, но это всё-таки не седьмая, а восьмая олимпиада