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

Задача в отпуске: дан массив A из N чисел (перестановка из 1..N) — старый список номеров вопросов в порядке старта. Нужно построить новый список B по правилу: - B[0] = A[0] (первый номер совпадает с первым в старом списке). - Далее выбираем номера так, чтобы каждый новый элемент максимально отдалялся по позициям в старом списке от уже выбранных. Расстояние измеряется как минимальное расстояние по индексам между новым и любым уже выбранным индексом. - Если таких номеров несколько, выбираем тот, который встречается раньше в старом списке. Делаем это за O(N log N) за счет разбиения отрезков (глобальная идея ниже). Пояснение идеи (пошагово, понятно даже школьнику) - Пусть мы уже выбрали некоторый набор позиций S в старом списке. Между соседними выбранными позициями образуются «пустые» отрезки (граня) между ними. В пределах каждогоSuch отрезка можно выбрать кандидат pos так, чтобы минимальное расстояние до S было максимально возможным внутри этого отрезка. - Для отрезка между двумя соседними выбранными индексами L и R (L < R) максимальное MinDist внутри этого отрезка равно floor((R - L) / 2). А сами кандидаты, достигающие этого, расположены в середине отрезка: - если R - L чётно: единственный середина pos = L + (R - L) / 2; - если R - L нечётно: две середины, но выбирается та с меньшим индексом (она же встречается раньше в старом списке). - Поэтому эффективный метод: держим в приоритетной очереди все currently существующие границы (граня) между соседними выбранными позициями. Для каждого грани (L, R) кампания кандидата — это pos = L + floor((R - L) / 2) и dist = floor((R - L) / 2). - Сначала у нас выбрано только A[0]. Затем явно возьмём A[N-1] (это следующий кандидат по правилу: максимальное расстояние до 0 — это N-1). - После этого между выбранными позициями 0 и N-1 образуется грань (0, N-1). В неё помещаем её середину и далее будем делить грани, добавляя новые грани после каждого выбора. - Тот кандидат, который в данный момент имеет максимальное dist; если нескольких — выбираем меньший pos (раньше в старом списке). Это естественно реализуется через приоритетную очередь, сортировку по (dist убыв., pos возрастан.). Алгоритм 1) B[0] = A[0]. Пометим позицию 0 как выбранную. 2) Если N >= 2, B[1] = A[N-1]. Пометим позицию N-1 как выбранную. 3) Если между 0 и N-1 есть хотя бы одна невыбранная позиция (то есть N > 2), добавим грань (0, N-1) в приоритетную очередь: - dist = floor((N-1 - 0) / 2) - pos = 0 + dist - сохраняем грань как (L=0, R=N-1, pos) - в очереди упорядочиваем по (dist по убыв., pos по возрастанию) 4) Пока не заполнен весь список (пока не выписано N чисел): - берём грань с максимальным dist и меньшим pos (по сути — извлекаем верхушку кучи по условию). - выбираем pos как следующий элемент: B[k] = A[pos]. - пометим pos как выбранный и удаляем этот грань. - разделяем грань на две новые: (L, pos) и (pos, R). Для каждой из них, если внутри есть невыбранные индексы, добавляем в очередь новый кандидат с: - dist' = floor((pos - L) / 2) для левой грани, pos' = L + dist' - dist'' = floor((R - pos) / 2) для правой грани, pos'' = pos + dist'' 5) Повторяем до заполнения N элементов. Сложность: каждое добавление/извлечение из очереди стоит O(log N). Всего добавляется не более N граней, итого O(N log N). Поскольку N ≤ 1e5, это нормально. Пример проверки (наглядно): - Пусть A = [1,2,3,4,5], N = 5. - B[0] = 1, B[1] = 5. - Грань (0,4): dist=2, pos=2. - Выбираем pos=2 → B[2] = 3. - Разделяем на (0,2) и (2,4). Их dist = 1, pos=1 и pos=3 соответственно. - Выбираем меньший pos среди тех с dist=1 → pos=1 → B[3] = 2. - Остался грань (2,4) с pos=3 → B[4] = 4. Итог: [1,5,3,2,4], что соответствует правилу. Код на Python (быстрая реализация с приоритетной очередью) ```python import sys import heapq def solve(): data = list(map(int, sys.stdin.read().strip().split())) if not data: return it = iter(data) N = next(it) A = [next(it) for _ in range(N)] B = [0] * N chosen = [False] * N # Шаг 1: берем первый элемент B[0] = A[0] chosen[0] = True idx = 1 # Шаг 2: если есть второй элемент, берем последний if N >= 2: B[1] = A[N - 1] chosen[N - 1] = True idx = 2 # Шаг 3: если есть внутри грань, добавляем её в очередь heap = [] if N - 1 - 0 > 1: # есть хотя бы один элемент между 0 и N-1 dist = (N - 1 - 0) // 2 pos = 0 + dist heapq.heappush(heap, (-dist, pos, 0, N - 1)) # Шаг 4: далее выбираем по правилу while idx < N and heap: negdist, pos, L, R = heapq.heappop(heap) dist = -negdist if chosen[pos]: continue # если уже выбрали по каким-то причинам B[idx] = A[pos] chosen[pos] = True idx += 1 # левая грань (L, pos) if pos - L > 1: d = (pos - L) // 2 mid = L + d heapq.heappush(heap, (-d, mid, L, pos)) # правая грань (pos, R) if R - pos > 1: d = (R - pos) // 2 mid = pos + d heapq.heappush(heap, (-d, mid, pos, R)) print(' '.join(map(str, B))) if __name__ == "__main__": solve() ``` Пояснение к коду - Первая и вторая выдачи (B[0] = A[0], B[1] = A[N-1]) реализуют начальные условия: первый номер совпадает с первым в старом списке, затем берётся самый дальний по индексу элемент. - Дальше мы храним грани между уже выбранными индексами в приоритетной очереди, сортируемой по (dist убыв., pos возрастание), чтобы выбирать в случае равных dist тот кандидат, который встречается раньше в старом списке. - После выбора позиции pos мы делим грань на две и добавляем новые кандидаты, если внутри граней есть ещё невыбранные элементы. Если вам нужно решение на другом языке (C++, Java и т.д.), скажите — могу привести аналогичный вариант на требуемом языке.