codeforces#P1531E2. Сортировка слиянием
Сортировка слиянием
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)
Как можно заметить, этот код использует логирование — важнейший инструмент разработки.
Старший разработчик ВКонтакте Вася сгенерировал перестановку (массив из различных целых чисел от до ), дал её на вход функции sort и получил на выходе строку . На следующий день строку Вася нашёл, а перестановка потерялась.
Вася хочет восстановить любую перестановку такую, что вызов функции sort от неё даст ту же строку . Помогите ему!
Ввод содержит непустую строку , состоящую из символов 0 и 1.
В этой версии задачи для любого теста существует перестановка длины не более , удовлетворяющая условию. Тем не менее, ваш ответ может иметь любую длину, в том числе превышающую .
В первой строке выведите целое число — длину перестановки.
Во второй строке выведите различных целых чисел () — элементы перестановки.
Если существует несколько вариантов ответа, выведите любой из них.
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