Единственное отличие между легкой и сложной версиями — длины строк. Вы можете взламывать эту задачу только тогда, когда решите обе задачи.
У Кёрка есть бинарная строка \(s\) (строка, содержащая только нули и единицы) длины \(n\), и он просит вас найти бинарную строку \(t\) такой же длины, для которой выполняются следующие условия:
- Для любых \(l\) и \(r\) (\(1 \leq l \leq r \leq n\)) длина наибольшей неубывающей подпоследовательности в подстроке \(s_{l}s_{l+1} \ldots s_{r}\) равна длине наибольшей неубывающей подпоследовательности в подстроке \(t_{l}t_{l+1} \ldots t_{r}\);
- Количество нулей в строке \(t\) — максимально возможное.
Неубывающая подпоследовательность в строке \(p\) — это такая последовательность индексов \(i_1, i_2, \ldots, i_k\), что \(i_1 < i_2 < \ldots < i_k\) и \(p_{i_1} \leq p_{i_2} \leq \ldots \leq p_{i_k}\). Число \(k\) называется длиной подпоследовательности.
Если существует несколько строк, удовлетворяющих условиям, то выведите любую.
Выходные данные
Выведите бинарную строку, для которой выполняются указанные условия. Если существует несколько таких строк, выведите любую.
Примечание
В первом примере:
- Для подстрок длины \(1\) длина наибольшей неубывающей подпоследовательности равна \(1\);
- Для \(l = 1, r = 2\) наибольшая неубывающая подпоследовательность для подстроки \(s_{1}s_{2}\) — \(11\), для подстроки \(t_{1}t_{2}\) — \(01\);
- Для \(l = 2, r = 3\) наибольшая неубывающая подпоследовательность для подстроки \(s_{2}s_{3}\) — \(1\), для подстроки \(t_{2}t_{3}\) — \(1\);
- Для \(l = 1, r = 3\) наибольшая неубывающая подпоследовательность для подстроки \(s_{1}s_{3}\) — \(11\), для подстроки \(t_{1}t_{3}\) — \(00\);
Второй пример аналогичен первому.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
110
|
010
|
|
2
|
010
|
010
|
|
3
|
0001111
|
0000000
|
|
4
|
0111001100111011101000
|
0011001100001011101000
|