← 返回题目列表

Codeforces · 1204/D2

D2. 柯克和二进制字符串(硬版)

中文机器翻译题面 查看原题

简单版本和困难版本之间的唯一区别是字符串的长度。如果你解决了这个问题,你就可以破解它。但只有解决了这两个问题,才能破解前一个问题。

Kirk 有一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ (由零和一组成的字符串),他要求你找到一个长度相同且满足以下条件的二进制字符串 $$$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$$$。

如果有多个子串满足条件,则输出任意一个。

输入

第一行包含长度不超过$$$10^5$$$的二进制字符串。

输出

输出满足上述条件的二进制字符串。如果有很多这样的字符串,则输出其中任何一个。

示例

输入 #1

110

输出 #1

010

输入 #2

010

输出 #2

010

输入 #3

0001111

输出 #3

0000000

输入#4

0111001100111011101000

输出#4

0011001100001011101000

注意

在第一个示例中:

- 对于长度为 $$$1$$$ 的子串,最长非递减子序列的长度为 $$$1$$$;
- 对于$$$l = 1,r = 2$$$,子串$$$s_{1}s_{2}$$$的最长非递减子序列是$$$11$$$,子串$$$t_{1}t_{2}$$$的最长非递减子序列是$$$01$$$;
- 对于$$$l = 1,r = 3$$$,子串$$$s_{1}s_{3}$$$的最长非递减子序列是$$$11$$$,子串$$$t_{1}t_{3}$$$的最长非递减子序列是$$$00$$$;
- 对于$$$l = 2,r = 3$$$,子串$$$s_{2}s_{3}$$$的最长非递减子序列是$$$1$$$,子串$$$t_{2}t_{3}$$$的最长非递减子序列是$$$1$$$;

第二个示例与第一个示例类似。