3-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

Задача C. Разделяем на пары

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Есть массив $a$ из $n$ целых чисел. Для каждого $k$ от 1 до $\lfloor \frac{n}{2} \rfloor$, найдите $k$ различных пар, что сумма абсолютных разностей пар была минимизирована. Более формально, выберите $2k$ различных индексов, и разбейте их на $k$ пар $(i_1, j_1), (i_2, j_2), \dots, (i_k, j_k)$, чтобы значение $|a_{i_1} - a_{j_1}| + |a_{i_2} - a_{j_2}| + \dots + |a_{i_k} - a_{j_k}|$ было минимально.

Формат входного файла

В первой строке находятся одно целое число $n$ ($1 <= n <= 2*10^5$). Во второй строке находятся $n$ целых чисел $a_1, a_2,…, a_n (1 <= a_i <= 10^9)$.

Формат выходного файла

Выведите $\lfloor \frac{n}{2} \rfloor$ целых чисел, где $k$-е число является ответом $k$ пар.

Система оценки

Данная задача содержит $6$ подзадач, в которых выполняются следующие ограничения:

1. $n <= 11$. Оценивается в $7$ баллов.
2. $n <= 18$. Оценивается в $11$ баллов.
3. $n <= 500$. Оценивается в $13$ баллов.
4. $n <= 5000$. Оценивается в $15$ баллов.
5. $a_i <= 5000$. Оценивается в $13$ баллов.
6. Исходные условия задачи. Оценивается в $41$ баллов.

Примеры:

Вход

6
1 3 5 8 13 21

Ответ

2 5 13

Вход

11
31 12 1 36 41 57 21 79 86 63 97

Ответ

5 11 18 27 39

( Narkhan Kamzabek )