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

Ниже — подробное решение и объяснение кода. Я объясню структуру, идею алгоритма и пройдусь по шагам на простом примере. Это подходит для общего школьного уровня и без привязки к конкретному предмету или классу. Цель кода - Построить последовательность чисел из заданного массива A так, чтобы следующие элементы выбирались по правилу, основанному на расстояниях между их исходными позициями и уже выбранной частью последовательности. - В частности, сначала берётся первый элемент A[0], затем последовательно добавляются другие элементы. На каждом шаге выбирается элемент с максимальным текущим расстоянием до уже включённых в результат позиций. Для отслеживания текущих ближайших позиций используется структура Treap. Что делает код, простыми словами - Мы держим множество S этих «позиций» — изначально в S есть только позиция 0. - Для каждого оставшегося элемента A[i] мы помечаем его как кандидата и запоминаем его начальное расстояние до S. - В глобальной очереди (куче) хранятся кандидаты с их текущим «приростом» дистанции. Мы берём самого дальнего кандидата и вспоминаем его исходное ожидание расстояния. - Но фактически расстояние от позиции i до множества S может измениться (когда мы добавим новые позиции в S). Поэтому каждый раз, когда мы извлекаем кандидата, мы пересчитываем его реальное дистанционное расстояние dcur до S: - если оно совпадает с тем расстоянием, которое было в очереди — принимаем этого кандидата (то есть добавляем A[i] в результат и добавляем позицию i в S); - если не совпадает — обновляем значение расстояния в очереди и возвращаем кандидата обратно в очередь. - Так мы гарантируем, что выбираем следующий элемент в порядке непрерывного изменения текущего расстояния до уже выбранных позиций. Ключевые структуры и функции - TreapNode: узел дерева (ключ — позиция в исходном списке, prio — приоритет для балансировки). - 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. Это делается через предшественника и преемника вtreap и берётся минимум разниц с pos_t. - main(): - считывает N и массив A; - создаёт первый элемент результата as A[0]; - S изначально содержит позицию 0 (вставляется в treap); - строит кучу кандидатов: для каждого i от 1 до N-1 кладём в кучу запись (dist, i, A[i]), где dist = i (расстояние до позиции 0 в начале); - пока результат не содержит N элементов: - вытаскиваем кандидата с максимальным dist; - вычисляем dcur = dist_to_S(i, treap); - если dcur != dist_in_heap, обновляем dist в кандидате и повторяем; - иначе принимаем кандидата: добавляем A[i] в результат и вставляем позицию i в treap (S grows). Почему этот подход корректен - Мы поддерживаем множесто позиций S, соответствующее уже выбранным элементам (их исходные позиции в A). - dist_to_S(i, S) даёт реальное расстояние от i до ближайшей позиции из S. - Хранение в куче изначальных расстояний и «ленивое» обновление позволяют выбрать на каждом шаге того кандидата, у которого на данный момент максимальное реальное расстояние до S. - После добавления новой позиции в S расстояния других кандидатов могут уменьшаться, что и отражается через повторное вычисление и обновление в очереди. Сложность - В среднем: вставка и поиск в treap — O(log N). - Операции в куче: каждая переоценка distance требует O(log N) времени на обновление кучи; каждая позиция может быть переоценена несколько раз, но в целом алгоритм работает за O(N log N) в среднем. - Память: O(N). Пример разбор на маленьком примере Пусть A = [7, 2, 9, 1, 5], N = 5. - Первый элемент результата: 7 (из A[0]). - S = {0} (позиция 0 в исходном списке). - Кандидаты (i, A[i], dist) на старте: - i=1, A[1]=2, dist=1 - i=2, A[2]=9, dist=2 - i=3, A[3]=1, dist=3 - i=4, A[4]=5, dist=4 - Извлекаем кандидат с максимальным dist: (4, 5, dist=4). dcur = dist_to_S(4, S) = |4-0| = 4 -> совпадает. Принимаем A[4]=5. Добавляем позицию 4 в S: S = {0,4}. - Теперь следующий кандидат: (3,1, dist=3). dcur = min(|3-0|, |4-3|) = min(3,1) = 1. dist_in_heap = 3. Они не равны, обновляем в куче dist=1 и возвращаем. - Далее возьмём (2,9, dist=2). dcur = min(|2-0|, |4-2|) = min(2,2) = 2. Совпадает; принимаем A[2]=9. S={0,4,2}. - Далее кандидат (3,1, dist=1). dcur = min(|3-2|, |3-4|) = min(1,1)=1. Совпадает; принимаем A[3]=1. S={0,4,2,3}. - Наконец остаётся i=1, A[1]=2. dcur = min(|1-0|, |1-2|, |1-3|, |1-4|) = min(1,1,2,3) = 1. Совпадает; принимаем 2. - Итог: результат = [7, 5, 9, 1, 2] (порядок может отличаться в зависимости от исходных расстояний и стечения обстоятельств, но принцип соблюдён). Особенности и замечания - В коде есть переменная pos, которая создаёт словарь значений value -> индекс, но она нигде не используется дальше. Это можно безопасно удалить без влияния на работу алгоритма. - random.seed(0xC0FFEE) фиксирует генерацию приоритетов Treap, чтобы поведение было детерминированным. - Ввод ожидается в формате: сначала N, затем N целых чисел A. - Если в A встречаются повторяющиеся значения, сами значения будут повторяться в результатe; код не полагается на уникальность значений, но словарь pos всё равно может иметь коллизии (но не используется в алгоритме). Кратко резюмируя - Код строит результат по принципу максимального текущего расстояния до уже выбранных исходных позиций, используя Treap для эффективного поиска ближайшей выбранной позиции и кучу для выбора кандидатов с максимальным расстоянием. - По шагам: выбираем первый элемент (A[0]), затем повторяем: смотрим следующий кандидат с наибольшим исходным расстоянием, проверяем текущее расстояние до S; если оно не совпадает — обновляем и перекидываем кандидата обратно в кучу; если совпадает — добавляем в результат и добавляем его позицию в S. - Сложность в среднем O(N log N) и подходит для средней школы как пример сочетания динамических структур данных (treap) и жадной стратегии. Если хотите, могу привести конкретный пошаговый разбор на ещё однойTiny конкретной последовательности или разобрать каждую строку кода с комментариями.