Профессор перед экзаменом попросил ассистента подготовить список номеров вопросов для каждого студента. Так как профессор планирует подробно спрашивать материал курса, то каждый…

Решение задачи и идея

• Пусть старый список задается как массив 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

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].
• Далее мы последовательно выбираем середины текущих сегментов между уже выбранными точками, выбирая сегменты по максимальному возможному расстоянию до ближайшего выбранного, и в случае равенства — меньший середины по порядку в старом списке. Это полностью соответствует условию задачи.

Если нужны дополнительные пояснения или тесты на конкретных примерах, скажите — могу разобрать подробно.