Сортировка слиянием

题目描述

Рассмотрим следующий код сортировки слиянием на языке Python: ``` <pre class="lstlisting">``` def sort(a):<br></br> n = len(a)<br></br> b = [0 for i in range(n)]<br></br> log = []<br></br><br></br> def mergeSort(l, r):<br></br> if r - l <= 1:<br></br> return<br></br> m = (l + r) >> 1<br></br> mergeSort(l, m)<br></br> mergeSort(m, r)<br></br> i, j, k = l, m, l<br></br> while i < m and j < r:<br></br> if a[i] < a[j]:<br></br> log.append('0')<br></br> b[k] = a[i]<br></br> i += 1<br></br> else:<br></br> log.append('1')<br></br> b[k] = a[j]<br></br> j += 1<br></br> k += 1<br></br> while i < m:<br></br> b[k] = a[i]<br></br> i += 1<br></br> k += 1<br></br> while j < r:<br></br> b[k] = a[j]<br></br> j += 1<br></br> k += 1<br></br> for p in range(l, r):<br></br> a[p] = b[p]<br></br><br></br> mergeSort(0, n)<br></br> return "".join(log)<br></br> ``` ``` Как можно заметить, этот код использует логирование — важнейший инструмент разработки. Старший разработчик ВКонтакте Вася сгенерировал перестановку $ a $ (массив из $ n $ различных целых чисел от $ 1 $ до $ n $ ), дал её на вход функции sort и получил на выходе строку $ s $ . На следующий день строку $ s $ Вася нашёл, а перестановка $ a $ потерялась. Вася хочет восстановить любую перестановку $ a $ такую, что вызов функции sort от неё даст ту же строку $ s $ . Помогите ему!

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

00000000000000000000000000000000

输出样例 #1

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

输入样例 #2

11111111111111111111111111111111

输出样例 #2

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

输入样例 #3

101011010001100100011011001111011000011110010

输出样例 #3

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

暂时还没有翻译