- Разнообразие товаров
Выдача бывает полезной, бывает информативной, а бывает разнообразной.
Разработайте алгоритм, который будет упорядочивать товары наиболее разнообразно.
Дана выборка товаров из разных категорий: producti, categoryi - идентификатор продукта и его категория.
Расположите объекты в таком порядке, чтобы минимальная разность позиций между товарами одной категории была как можно больше.
Если все товары различных категорий, то расположите их в произвольном порядке.
Формат ввода
В первой строке записано одно целое число n (1≤n≤100000) - количество товаров в списке.
Далее в каждой из n строк через пробел записано по два целых числа producti и categoryi (0≤producti,categoryi≤230) - id продукта и его категория.
Гарантируется, что все величины producti различны.
Формат вывода
Выведите nn целых чисел producti - некоторая перестановка величин.
Для результирующего порядка значение наименьшего расстояния между товарами одной категории должно быть максимальным возможным.
Если подходящих перестановок товаров несколько, выведите любую из них.