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

Решение на Python 3.11 Задача сводится к следующему: - Пусть старый список вопросов задаётся как перестановка old[0..N-1]. - Мы формируем новый список Q[0..N-1], где: - Q[0] = old[0] (первый элемент старого списка). - Q[1] = old[N-1] (поскольку это максимизирует минимальное расстояние до уже выбранного 0-го элемента). - Для каждого следующего элемента выбираем такую позицию p в старом списке, которая не выбрана ранее, чтобы минимальное расстояние по позициям в старом списке до уже выбранных позиций было максимально possible. При равенстве расстояний выбираем позицию с меньшим индексом в старом списке (то есть идёт раньше в старом списке). Идея: - Рассматриваем позиции в старом списке как точки на оси от 0 до N-1. - Уже выбранны позиции: 0 и N-1. - Между соседними выбранными позициями a и b лежит так называемая «дыра» (gap). Любая невыбранная позиция p внутри этой дырки имеет расстояние min(p-a, b-p) до ближайшей выбранной позиции. Максимум внутри дырки достигается в середине: p = floor((a+b)/2), и значение дистанции равно floor((b-a)/2). - Чтобы выбрать следующий элемент по правилу задачи, достаточно всегда брать дырку с максимальным floor((b-a)/2); если таких дырок несколько, выбрать середину с наименьшим п (то есть меньший индекс p). Так мы реализуем tie-break «идёт раньше в старом списке». - Мы будем поддерживать структуру дырок между соседними выбранными позициями в виде связанных между собой элементов и при каждом выборе раскладывать одну дырку на две меньшие. Для эффекта быстрого выбора используем max-heap (при помощи отрицательного расстояния) и lazy-проверку валидности дырки. Алгоритм: - Пусть выбранные позиции S начинаются как {0, N-1}. - Имеем две структуры: - left[i], right[i] — соседние выбранные позиции слева и справа от i в упорядоченном по индексу наборе выбранных позиций. - chosen[i] — флаг выбранной позиции. - В куче хранится дырка (a, b) между соседними выбранными a и b (то есть right[a] == b). Для каждой дырки вычисляются: - dist = floor((b-a)/2) - candidate p = floor((a+b)/2) - запись в куче: (-dist, p, a, b) - Вытаскивая дырку, проверяем валидность: дырка действительно между соседними выбранными (right[a] == b). Если нет — пропускаем. - Выбираем p = floor((a+b)/2), кладём old[p] в Q, помечаем p как выбранный и вставляем его между a и b, образуя две новые дырки: (a, p) и (p, b), если внутри них есть место (т.е. b-a > 1 и p-a > 1 соответственно). - Повторяем до заполнения N элементов. Сложность: каждый элемент добавляется в структуру дырок ограниченное число раз, операции в куче — O(log N). В целом O(N log N) по времени и O(N) по памяти. Код (Python 3.11): ```python import sys import heapq def solve(): data = list(map(int, sys.stdin.buffer.read().split())) if not data: return it = iter(data) N = next(it) old = [next(it) for _ in range(N)] # Ответ: заполняем новым списком Q Q = [0] * N Q[0] = old[0] if N >= 2: Q[1] = old[N - 1] if N <= 2: print(' '.join(map(str, Q[:N]))) return # Данные структуры для динамических дырок left = [-1] * N right = [-1] * N chosen = [False] * N # Изначально выбраны позиции 0 и N-1 chosen[0] = True chosen[N - 1] = True left[0] = -1 right[0] = N - 1 left[N - 1] = 0 right[N - 1] = -1 # Max-heap по дистанциям; храним (-dist, mid, a, b) heap = [] # Граница дырки между 0 и N-1 if N - 1 - 0 > 1: dist0 = (N - 1 - 0) // 2 mid0 = (0 + (N - 1)) // 2 heapq.heappush(heap, (-dist0, mid0, 0, N - 1)) idx = 2 # текущая позиция в Q, уже заполнены 0 и 1 while idx < N: # Найти валидную дырку while heap: negdist, _mid, a, b = heap[0] if right[a] == b: # дырка действительно между соседними a и b break heapq.heappop(heap) if not heap: break # неожиданный случай, но защитим # Берём верхнюю дырку heapq.heappop(heap) a, b = a, b # переменные уже заданы p = (a + b) // 2 # середина дырки Q[idx] = old[p] idx += 1 # Вставляем p между a и b chosen[p] = True right[a] = p left[p] = a right[p] = b left[b] = p # Добавляем две новые дырки (a, p) и (p, b) при необходимости if p - a > 1: dist_left = (p - a) // 2 p_left = (a + p) // 2 if dist_left > 0: heapq.heappush(heap, (-dist_left, p_left, a, p)) if b - p > 1: dist_right = (b - p) // 2 p_right = (p + b) // 2 if dist_right > 0: heapq.heappush(heap, (-dist_right, p_right, p, b)) print(' '.join(map(str, Q))) if __name__ == "__main__": solve() ``` Кратко о корректности: - Первый элемент всегда old[0], второй — old[N-1], так как это максимизирует минимальное расстояние к уже выбранному элементу на стадии выбора второго. - После этого, дырки между соседними выбранными позициями полностью описывают текущее состояние набора выбранных позиций. В каждой дырке максимум минимального расстояния достигается в середине дырки, и tie-break по меньшему индексу соответствует выбору меньшего p. - Проверка валидности дырки осуществляется лениво через right[a] == b; при вставке нового элемента старые дырки корректно распадаются на две новые, которые добавляются в кучу за счёт соответствующих(dist, mid, a, b) значений. Это решение удовлетворяет ограничениям N ≤ 100000 и работает за O(N log N) времени.