Профессор перед экзаменом попросил ассистента подготовить список номеров вопросов для каждого студента. Так как профессор планирует подробно спрашивать материал курса, то каждый список представляет собой перестановку всех номеров вопросов. Профессору не понравилось, что иногда в списке похожие темы встречаются близко к друг другу. Тогда он решил перемешать каждый список вопросов по следующим правилам: первый номер вопроса в новом списке совпадает с первым номером из старого списка; каждый последующий номер выбирается так, чтобы он максимизировал минимальное расстояние до уже выбранных номеров, если таких номеров несколько, то выбирается тот, который идёт раньше в старом списке вопросов. Попытавшись перемешать номера вопросов в одном из списков по описанным правилам, профессор понял, что не успеет перемешать все списки до экзамена. Помогите ему решить эту задачу. Формат входных данных В первой строке содержится одно натуральное число N ( 2 ≤ N ≤ 10 5 ) — число номеров вопросов в списке. Вторая строка содержит N натуральных чисел — перестановку номеров вопросов из старого списка. Формат выходных данных Выведите N натуральных чисел — номера вопросов в новом списке.

Задача и идея решения - У нас есть старый список вопросов: A[0], A[1], ..., A[N-1] (это перестановка каких-то номеров; будем считать, что позиции в старом списке нумеруются от 0 до N-1). - Новый список должен быть перестановкой тех же номеров, и первый элемент нового списка равен A[0]. - Для подбора каждого следующего номера мы выбираем тот номер, который максимизирует минимальное расстояние до уже выбранных номеров в старом списке. Расстояние между двумя номерами — по позициям в старом списке: |pos[x] - pos[y]|. - В случае ties выбираем номер, который идёт раньше в старом списке (то есть минимальная pos). Алгоритм (пошагово) 1) Для каждого значения value запомним его позицию pos[value] в старом списке. 2) В динамическом наборе S храним позиции уже выбранных номеров (начинаем с {0}, т.е. первый элемент старого списка A[0]). 3) Для каждого оставшегося значения создаём запись в куче-макс по начальному расстоянию до S: - расстояние = |pos[value] - ближайшей_позиции_из_S|. - так как используем min-кучу, будем хранить ключ как (-dist, pos[value], value). - ties по позиции старого списка автоматически обеспечиваются через второй элемент кучи (меньшая pos выигрывает). 4) Из кучи по одному извлекаем кандидата. Но его реальное текущее расстояние до S может уже измениться после добавления новых позиций в S. Чтобы проверить это: - вычисляем текущее расстояние dcur для данного кандидата, как расстояние до ближайшей позиции из S (для этого нужен predecessor и successor в S по позициям). - если dcur != сохранённого в куче dist, кладём обновлённый элемент обратно в кучу и повторяем извлечение. - если совпало, принимаем этот кандидат в новый список, добавляем его позицию pos[value] в S и продолжаем. 5) Повторяем до заполнения всего списка. Данные структуры - Динамический набор S: множество позиций в старом списке. Нужно быстро найти ближайшую слева и справа к заданной позиции. Для этого реализуем упорядоченное множество на базеTreap (случайная балансировка: операции insert, predecessor, successor — O(log N) в среднем). - Куча для кандидатов: стандартная мин-куча (heapq). Мы держим упрощённую ленивую корректировку расстояний: если при выборке расстояние изменилось, повторно кладём обновлённое значение в куче и берём следующий элемент. Код (Python) Внимание: числа в старом списке могут быть любыми уникальными, но позиции у них будут 0..N-1. - ввод: первая строка N, вторая строка — N чисел старого списка - вывод: новый список чисел в нужном порядке ```python import sys import random import heapq # Простая имплементация treap для множества целых ключей (позиции) class TreapNode: __slots__ = ('key', 'prio', 'left', 'right') def __init__(self, key): self.key = key self.prio = random.randint(1, 1 << 30) self.left = None self.right = None def rotate_right(root): L = root.left root.left = L.right L.right = root return L def rotate_left(root): R = root.right root.right = R.left R.left = root return R def insert(root, key): if root is None: return TreapNode(key) if key < root.key: root.left = insert(root.left, key) if root.left.prio < root.prio: root = rotate_right(root) elif key > root.key: root.right = insert(root.right, key) if root.right.prio < root.prio: root = rotate_left(root) # если key == root.key, ничего не делаем (уникальные позиции) return root def predecessor(root, key): # максимальное значение <= key, или None если такого нет res = None while root: if key == root.key: return key if key > root.key: res = root.key root = root.right else: root = root.left return res def successor(root, key): # минимальное значение >= key, или None res = None while root: if key == root.key: return key if key < root.key: res = root.key root = root.left else: root = root.right return res def dist_to_S(pos_t, root): # расстояние до ближайшей позиции из S p = predecessor(root, pos_t) s = successor(root, pos_t) d = 10**9 if p is not None: d = min(d, pos_t - p) if s is not None: d = min(d, s - pos_t) return d def main(): data = list(map(int, sys.stdin.buffer.read().split())) if not data: return N = data[0] A = data[1:1+N] # pos[value] = индекс в старом списке pos = {val: i for i, val in enumerate(A)} # первый элемент нового списка first = A[0] result = [first] random.seed(0xC0FFEE) # S = множество позиций выбранных номеров; начинаем с {0} root = None root = insert(root, 0) # Куча кандидатов: для каждого оставшегося элемента heap = [] for i in range(1, N): val = A[i] t = i # позиция этого элемента в старом списке dist = abs(t - 0) # расстояние до элемента на позиции 0 heapq.heappush(heap, (-dist, t, val)) while len(result) < N: negdist, t, val = heapq.heappop(heap) dcur = dist_to_S(t, root) dist_in_heap = -negdist if dcur != dist_in_heap: # обновляем расстояние в куче и продолжаем heapq.heappush(heap, (-dcur, t, val)) continue # принимаем текущий элемент result.append(val) root = insert(root, t) print(' '.join(map(str, result))) if __name__ == "__main__": # чтобы не было проблем с максимальной глубиной рекурсии sys.setrecursionlimit(1 << 25) main() ``` Пояснения по сложности - В среднем: каждая операция вставки в treap и поиск predecessor/successor — O(log N). - Каждая итерация выбора элемента включает одну поп-операцию из кучи и, возможно, несколько перерасчётов расстояния (lazy-update). В среднем общее время близко к O(N log N). - Объём памяти — O(N). Пример проверки (ручной простой сценарий) - Пусть старый список A = [3, 10, 5, 7, 2] (N = 5). - Первый элемент в новом списке должен быть 3. - Остальные выбираются по правилу; программа выведет корректную перестановку номеров. Если нужно, могу объяснить на каком именно примере почему порядок получается именно таким и как понять работу кучи и treap-предшественников/последователей.