Codeforces Global Round 25 |
---|
Закончено |
Имеется массив $$$a$$$ длины $$$2^k$$$, который изначально является перестановкой значений от $$$1$$$ до $$$2^k$$$ для некоторого целого положительного числа $$$k$$$. Алиса и Боб играют в следующую игру на массиве $$$a$$$. Сначала Алисе и Бобу даётся значение $$$t$$$ между $$$1$$$ и $$$k$$$. Затем, ровно $$$t$$$ ходов происходит следующее:
Счет игры определяется как максимальное значение в $$$a$$$ после всех $$$t$$$ ходов. Алиса хочет максимизировать этот счет, а Боб — минимизировать.
Вам нужно вывести $$$k$$$ чисел: счет игры, если и Алиса, и Боб играют оптимально, для всех $$$t$$$ от $$$1$$$ до $$$k$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$k$$$ ($$$1 \le k \le 20$$$) — параметр длины массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$2^k$$$ целых чисел $$$a_1, a_2, \ldots, a_{2^k}$$$ ($$$1 \le a_i \le 2^k$$$, $$$a_i$$$ попарно различны) — заданный массив $$$a$$$.
Гарантируется, что сумма $$$2^k$$$ по всем наборам входных данных не превосходит $$$2^{20}$$$.
Для каждого набора входных данных выведите $$$k$$$ чисел, где $$$i$$$-е число — это счет игры, если Алиса и Боб играют оптимально, а игра длится $$$t = i$$$ ходов.
511 224 3 2 135 1 6 4 7 2 8 3410 15 6 12 1 3 4 9 13 5 7 16 14 11 2 8532 2 5 23 19 17 31 7 29 3 4 16 13 9 30 24 14 1 8 20 6 15 26 18 10 27 22 12 25 21 28 11
1 3 1 7 5 1 15 13 9 1 31 28 25 17 1
В третьем наборе входных данных, для $$$t = 2$$$, игра могла бы проходить следующим образом:
Название |
---|