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

Решение задачи и идея - Пусть старый список задается как массив P длины N. Первый элемент нового списка должен быть тем же элементом P[0]. - Пусть мы ориентируемся на позиции в старом списке: 0, 1, ..., N-1. Начальное выбранное положение — 0 (это P[0]). - В каждом шаге мы выбираем следующий элемент так, чтобы минимальное расстояние до уже выбранных позиций было максимальным. Расстояние между двумя позициями — это разность их индексов. - Важно заметить: после выбора 0 следующим становится N-1 (последний элемент старого списка), потому что расстояние до 0 максимально. - Далее можно рассуждать через сегменты между уже выбранными точками. Если между двумя соседними выбранными позициями a и b есть еще невыбранная позиция, то ближайшее выбранное расстояние для самой лучшей кандидатуры внутри этого сегмента достигается в середине, m = floor((a + b) / 2). Значение расстояния равно floor((b − a) / 2). Среди сегментов с максимальным расстоянием выбор делается по меньшему m (то есть тому, который идёт раньше в старом списке), что совпадает с условиями задачи. - Эту стратегию можно реализовать с помощью кучи-очереди (макс-heap по расстоянию). Мы будем держать сегменты между уже выбранными точками; каждый сегмент [a, b] задаёт кандидата m = floor((a + b)/2) и расстояние d = floor((b − a)/2). Мы выбираем сегмент с максимальным d, при равных d — сегмент с меньшим m. После выбора m сегмент делится на [a, m] и [m, b], и эти сегменты снова участвуют в выборах. Алгоритм - Инициализация: order = [0]. Если N > 1, добавляем N−1 как второй элемент: order = [0, N−1]. - В куче храним сегменты [a, b] в виде кортежей (-d, m, a, b), где d = (b − a) // 2 и m = (a + b) // 2. Мы добавляем в кучу сегмент [0, N−1] только если в нём есть interiores (b − a ≥ 2). - Пока количество элементов в order меньше N: - Берём сверху сегмент с максимальным d и минимальным m. - Добавляем m в order. - Раскладываем сегмент на [a, m] и [m, b] и добавляем их в кучу, если внутри них есть interior точки (то есть соответствующие длины больше или равны 2). После построения порядка индексов order получаем новый список как arr[order[0]], arr[order[1]], ..., arr[order[N−1]]. Сложности - Время: O(N log N) за счёт очереди при добавлении midpoints. - Память: O(N). Пример реализации на Python 3 ```python import sys import heapq def main(): data = list(map(int, sys.stdin.buffer.read().split())) if not data: return it = iter(data) N = next(it) arr = [next(it) for _ in range(N)] if N == 1: print(arr[0]) return # Порядок индексов в новом списке order = [0, N - 1] # Куча сегментов [a, b] с их кандидатами m и расстоянием d # Храним как (-d, m, a, b) чтобы получить максимальное d, а при равных - минимальное m heap = [] a, b = 0, N - 1 if b - a >= 2: d = (b - a) // 2 m = (a + b) // 2 heapq.heappush(heap, (-d, m, a, b)) while len(order) < N: negd, m, a, b = heapq.heappop(heap) order.append(m) # левая часть [a, m] if m - a >= 2: d1 = (m - a) // 2 m1 = (a + m) // 2 heapq.heappush(heap, (-d1, m1, a, m)) # правая часть [m, b] if b - m >= 2: d2 = (b - m) // 2 m2 = (m + b) // 2 heapq.heappush(heap, (-d2, m2, m, b)) # Формируем ответ: перестановка старого списка по полученным индексам result = [str(arr[idx]) for idx in order] print(' '.join(result)) if __name__ == "__main__": main() ``` Пояснение по примерам и корректности - Первый элемент нового списка точно равен P[0]. - Второй элемент — P[N−1], так как это единственный кандидат с максимальным минимальным расстоянием до P[0]. - Далее мы последовательно выбираем середины текущих сегментов между уже выбранными точками, выбирая сегменты по максимальному возможному расстоянию до ближайшего выбранного, и в случае равенства — меньший середины по порядку в старом списке. Это полностью соответствует условию задачи. Если нужны дополнительные пояснения или тесты на конкретных примерах, скажите — могу разобрать подробно.