Сортировка слиянием
Contest: VK Cup 2021 - Квалификация (Engine)
Tags: *special, binary search

Рассмотрим следующий код сортировки слиянием на языке Python:

Как можно заметить, этот код использует логирование — важнейший инструмент разработки.

Старший разработчик ВКонтакте Вася сгенерировал перестановку $$$a$$$ (массив из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$), дал её на вход функции sort и получил на выходе строку $$$s$$$. На следующий день строку $$$s$$$ Вася нашёл, а перестановка $$$a$$$ потерялась.

Вася хочет восстановить любую перестановку $$$a$$$ такую, что вызов функции sort от неё даст ту же строку $$$s$$$. Помогите ему!

Input format:
Ввод содержит непустую строку $$$s$$$, состоящую из символов 0 и 1.

В этой версии задачи для любого теста существует перестановка длины не более $$$10^5$$$, удовлетворяющая условию. Тем не менее, ваш ответ может иметь любую длину, в том числе превышающую $$$10^5$$$.

Output format:
В первой строке выведите целое число $$$n$$$ — длину перестановки.

Во второй строке выведите $$$n$$$ различных целых чисел $$$a_0, a_1, \ldots, a_{n-1}$$$ ($$$1 \le a_i \le n$$$) — элементы перестановки.

Если существует несколько вариантов ответа, выведите любой из них.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
00000000000000000000000000000000

Example output:
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Example input:
11111111111111111111111111111111

Example output:
16
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

Editorial:
Чтобы ускорить решение, вместо линейного поиска по $$$n$$$ будем использовать бинарный.
Оказывается, что если по итогам сортировки при некотором $$$n$$$ использованы не все символы лога, значение $$$n$$$ точно нужно увеличить. Аналогично, если нам требуется взять символ из лога, когда их там уже не осталось, значение $$$n$$$ точно нужно уменьшить.
Как это доказать? Посмотрим на длины сортируемых отрезков перестановки в том порядке, в котором информация о них записана в логе. Например, при $$$n = 8$$$ получим последовательность $$$2, 2, 4, 2, 2, 4, 8$$$.
Увеличим $$$n$$$ на единицу. Заметим, что в дереве рекурсии произойдут следующие изменения: на некотором пути от корня до листа все длины отрезков увеличатся на $$$1$$$, а также появятся два новых листа. С точки зрения последовательности длин, описанной выше, изменения будут следующие: некоторые длины увеличатся на $$$1$$$, а также появится новый отрезок длины $$$2$$$. Например, при $$$n = 9$$$ получим последовательность $$$2, 2, 4, 2, \underline{3}, \mathit{2}, \underline{5}, \underline{9}$$$. Подчёркнуты увеличившиеся числа, а курсивом выделено новое число.
Для слияния на отрезке длины $$$k$$$ мы используем символы из лога, пока не встретим хотя бы $$$\lfloor \frac{k}{2} \rfloor$$$ нулей или хотя бы $$$\lceil \frac{k}{2} \rceil$$$ единиц. Пусть мы начали обработку отрезка длины $$$k$$$, находясь в логе на позиции $$$l$$$, а закончили на позиции $$$r$$$. Заметим, что если мы начнём на позиции $$$l' \ge l$$$, то закончим на позиции $$$r' \ge r$$$. Кроме того, если увеличить $$$k$$$, позиция конца также не может уменьшиться.
Так как при увеличении $$$n$$$ в последовательности длин отрезков не поменялся относительный порядок, а только увеличились некоторые элементы и добавились новые, можно видеть, что позиция, на которой мы закончим обработку лога, может сдвинуться только вправо. Следовательно, по величине $$$n$$$ можно выполнить бинарный поиск.
Проверка одного значения $$$n$$$ всё ещё выполняется за $$$O(n \log n)$$$, но в процессе бинарного поиска мы проверим только $$$O(\log n)$$$ различных значений, поэтому итоговая сложность составит $$$O(n \log^2 n)$$$.
Пример решения на Python: