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()

Краткое пояснение задачи и алгоритма - По входным данным читается количество элементов N и массив A из N целых чисел. - Программа строит новый порядок элементов массива A. Начинает с первого элемента (A[0]), затем последовательно добавляет остальные элементы. - Правило выбора следующего элемента: на каждом шаге выбирается оставшийся элемент, расстояние по индексам от него до уже выбранных позиций максимально. То есть выбираем элемент, чьё ближайшее соседнее положение в уже выбранном множестве позиций максимально далеко. - Для поддержания множества выбранных позиций используется простая структура Treap (быстрый случайно-упорядоченныйBST). В ней хранятся индексы (позиций) из старого списка, которые уже вошли в новый результат. - В процессе выбираются кандидаты через кучу с приоритетами по текущему расстоянию до S (множество избранных позиций). Чтобы не пересчитывать расстояния для всех элементов каждый раз, применяется «ленивая» проверка: если текущий зачищенный приоритет не совпадает с реальным расстоянием до S, элемент повторно вставляется в кучу с обновленным значением расстояния. - Это дает асимптотику примерно O(N log N) в среднем. Что делает код по шагам 1) Ввод - N — количество элементов. - A — список из N целых чисел. 2) Подготовка - first = A[0]. Результат пока содержит этот элемент: result = [first]. - S — множество позиций, уже взятых в новый порядок. Изначально S = {0}. Реализация S — это множество целых чисел индексов, хранящееся в Treap. - Эталонная фиксация случайности: random.seed(0xC0FFEE) для детерминированных приоритетов узлов Treap. 3) Кандидаты - Для каждого i от 1 до N-1 создаётся кандидат: t = i (позиция в старом списке), val = A[i]. - Расстояние до S на старте считается как dist = abs(t - 0) (поскольку S = {0} на старте). - Все кандидаты кладутся в кучу heap как кортеж (-dist, t, val). Минус перед dist делает кучу максимальной по dist (почему так делается: в Python heapq — минимальная куча). 4) Основной цикл - Пока результат содержит меньше N элементов: - Из кучи извлекается кандидат с наибольшим текущим «dist_in_heap» (для него берётся negdist -> dist_in_heap). - Вычисляется dcur = dist_to_S(t, root), то есть текущее минимальное расстояние от позиции t до ближайшей позиции в S (пользуясь predecessor/successor из Treap). - Если dcur != dist_in_heap, значит расстояние изменилось после прошлой вставки элементов в S. В таком случае обновляем запись в кучу новым значением расстояния и продолжаем (не добавляем этот элемент в результат пока расстояния не стабилизируются). - Если dcur == dist_in_heap, безопасно «покупаем» этот элемент: добавляем val к результату и вставляем позицию t в S (treap). Далее цикл продолжается. 5) Вывод - Выводится полученный порядок значений result через пробел. Ключевые данные структуры и функции - TreapNode: узел дерева поиска со случайным приоритетом (prio). Хранит key, left, right. - rotate_right / rotate_left: базовые вращения для поддержания свойств Treap. - insert(root, key): вставка ключа в Treap. Новые ключи уникальны (для позиций). - predecessor(root, key): возвращает максимально не превосходящее key значение в дереве, либо None. - successor(root, key): возвращает минимальное значение, не меньше чем key, либо None. - dist_to_S(pos_t, root): вычисляет расстояние от позиции pos_t до ближайшей позиции в S. Выбирает минимум из (pos_t - p) и (s - pos_t) для ближайших предшественника p и successor s в дереве S. Пояснение на простом примере Допустим, N = 5, A = [7, 3, 9, 1, 4]. - first = 7, result = [7], S = {0}. - Кандидаты: (t, val) = (1,3) dist=1; (2,9) dist=2; (3,1) dist=3; (4,4) dist=4. Все в куче. - Извлекаем самый дальний: t=4, val=4. dcur = dist_to_S(4, {0}) = 4. Совпадает — добавляем 4 в результат: result=[7,4], S={0,4}. - Обновляем расстояния для других кандидатов ленивая проверка потребует обновления: например для t=3 реальное dcur станет 1 (поскольку ближайшие позиции — 0 и 4). Поэтому мы переразмещаем этот кандидат в куче с dist=1 и пропускаем. - Далее выбираем t=2, val=9. dcur = dist_to_S(2, {0,4}) = 2. Совпадает — добавляем 9: result=[7,4,9], S={0,4,2}. - Далее t=1, val=3. dcur = dist_to_S(1, {0,4,2}) = 1. Совпадает — добавляем 3: result=[7,4,9,3], S={0,4,2,1}. - Остаётся t=3, val=1. dcur = dist_to_S(3, {0,4,2,1}) = 1. Совпадает — добавляем 1: результат = [7,4,9,3,1]. Почему так работает - Treap обеспечивает быстрый поиск predecessor/successor и вставку, что позволяет эффективно поддерживать множество выбранных позиций S. - Lazy-подход к обновлению расстояний в куче существенно экономит время: не пересчитываем dist для всех кандидатов на каждом шаге, а только когда они извлекаются и требуется проверка их актуальности. - В итоге получаем упорядочивание элементов массива A согласно правилу максимального расстояния до уже выбранных позиций по старому индексу. Возможные замечания - Предполагается, что в A могут быть повторяющиеся значения, но позиции в исходном списке уникальны. В S хранятся именно позиции (индексы), чтобы различать элементы с одинаковыми значениями. - Программа использует детерминированное семя случайности, чтобы результат был воспроизводимым. Когда может пригодиться такой подход - Если задача формулируется как построение порядка элементов так, чтобы каждый следующий элемент был как можно дальше от ранее выбранных позиций по индексу, или как построение перестановки с равными по смыслу условиям максимизации минимального расстояния к уже выбранным элементам. Если хочешь, могу привести ещё один конкретный пример или разобрать работу куска кода по шагам на этом примере.