| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 14 | 6 | 4 | 50.000% |
Вчера Альф в очередной раз провинился --- опять чуть не съел Лаки. На этот раз Вилли решил проучить Альфа.
В кладовке у него как раз завалялись $n+1$ очередь и $n$ стеков. Причем в одной из очередей также находилось 2ドル^n$ различных целых чисел от 1ドル$ до 2ドル^n$. Вилли выложил перед Альфом все очереди и стеки в чередующемся порядке --- сначала идет очередь, потом стек, потом опять очередь, и так далее, последней Вилли выложил очередь. Причем очередь с числами оказалась первой.
Все, что Альф может делать с этими стеками и очередями --- вынуть из структуры данных номер $i$ первое число (для стека это число на вершине, для очереди --- число, находящееся в голове) и добавить его в структуру данных номер $i+1$ (в случае стека число добавится на его вершину, в случае очереди --- в хвост). Теперь Вилли просит Альфа отсортировать все числа из первой очереди --- сделать несколько операций над этими структурами данных, чтобы все числа находились в последней очереди, а также располагались там в возрастающем порядке. То есть должно быть выполнено, что в голове очереди находится число 1ドル,ドル в хвосте очереди --- 2ドル^n,ドル а между ними числа должны быть отсортированы.
Вилли утверждает, что отсортировать числа гарантированно можно за 2ドル \cdot 2^{n} \cdot n$ операций. Помогите Альфу понять, как нужно применять эти операции, чтобы выполнить задание Вилли.
В первой строке входного файла дано целое число $n$ (1ドル \le n \le 15$) --- число стеков. Во второй строке входного файла дано 2ドル^n$ различных чисел $a_i$ (1ドル \le a_i \le 2^n$) --- исходный набор чисел.
В первой и единственной строке выходного файла выведите 2ドル \cdot 2^{n} \cdot n$ чисел $b_i$ (1ドル \le b_i \le 2n$) --- номер структуры данных, из которой извлекается число на $i$-м шаге вашего решения. Данная структура не должна быть пуста.
1 1 2
1 2 1 2
1 2 1
1 1 2 2