codeforces#P1531E2. Сортировка слиянием

    ID: 32128 problem_type.undefined ms MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>*special problem*special problembrute force

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

Cannot parse: NaNs error parsing time

Description

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

def sort(a):
  n = len(a)
  b = [0 for i in range(n)]
  log = []

def mergeSort(l, r): if r - l <= 1: return m = (l + r) >> 1 mergeSort(l, m) mergeSort(m, r) i, j, k = l, m, l while i < m and j < r: if a[i] < a[j]: log.append('0') b[k] = a[i] i += 1 else: log.append('1') b[k] = a[j] j += 1 k += 1 while i < m: b[k] = a[i] i += 1 k += 1 while j < r: b[k] = a[j] j += 1 k += 1 for p in range(l, r): a[p] = b[p]

mergeSort(0, n) return "".join(log)

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

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

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

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

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

В первой строке выведите целое число nn — длину перестановки.

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

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

</p>

Input

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

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

Output

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

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

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

Samples

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