import sys import random import heapq # Простая имплементация treap для множества целых ключей (позиции) class TreapNode: __slots__ = ('key', 'prio', 'left', 'right') def…
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) в среднем.
Что делает код по шагам
- Ввод
- N — количество элементов.
- A — список из N целых чисел.
- Подготовка
- first = A[0]. Результат пока содержит этот элемент: result = [first].
- S — множество позиций, уже взятых в новый порядок. Изначально S = {0}. Реализация S — это множество целых чисел индексов, хранящееся в Treap.
- Эталонная фиксация случайности: random.seed(0xC0FFEE) для детерминированных приоритетов узлов Treap.
- Кандидаты
- Для каждого i от 1 до N-1 создаётся кандидат: t = i (позиция в старом списке), val = A[i].
- Расстояние до S на старте считается как dist = abs(t - 0) (поскольку S = {0} на старте).
- Все кандидаты кладутся в кучу heap как кортеж (-dist, t, val). Минус перед dist делает кучу максимальной по dist (почему так делается: в Python heapq — минимальная куча).
- Основной цикл
- Пока результат содержит меньше 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). Далее цикл продолжается.
- Вывод
- Выводится полученный порядок значений 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 хранятся именно позиции (индексы), чтобы различать элементы с одинаковыми значениями.
- Программа использует детерминированное семя случайности, чтобы результат был воспроизводимым.
Когда может пригодиться такой подход
- Если задача формулируется как построение порядка элементов так, чтобы каждый следующий элемент был как можно дальше от ранее выбранных позиций по индексу, или как построение перестановки с равными по смыслу условиям максимизации минимального расстояния к уже выбранным элементам.
Если хочешь, могу привести ещё один конкретный пример или разобрать работу куска кода по шагам на этом примере.
