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)))
Ниже — подробное решение и объяснение кода. Я объясню структуру, идею алгоритма и пройдусь по шагам на простом примере. Это подходит для общего школьного уровня и без привязки к конкретному предмету или классу.
Цель кода
- Построить последовательность чисел из заданного массива 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 конкретной последовательности или разобрать каждую строку кода с комментариями.
