A48697.午枫爱操作

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小午有一个长度为 nn 的二进制数 ss ,这个二进制数从左往右的第 ii 位数为 sis_i ,小枫可以对这个二进制数做任意次(可以不做)操作:

  • 选择一段区间 [l,r][l,r] 满足 1l<rn,sl=0,sr=11 \leq l < r \leq n, s_l=0,s_r=1
  • 对于这段区间的每一位数 si(lir)s_i(l\leq i \leq r) ,将其变为 si1s_i \oplus 1 ,其中 \oplus 表示按位异或。

小午想通过小枫的操作让这个二进制数变得尽量大,请问这个数最大是多少,以二进制形式输出。

输入格式

第一行输入一个正整数 nn ,表示二进制串的长度 (1n106)(1\leq n\leq 10^6)

第二行输入一个长度为 nn 的二进制串 ss ,保证 ss 仅由 0011 构成且不含前导 00

输出格式

输出一个二进制串,表示小午能得到的最大的二进制数是多少。

输入输出样例

  • 输入#1

    5
    11101

    输出#1

    11110

说明/提示

样例解释:选择区间 [4,5][4,5] ,这个二进制数会变为 1111011110 ,已经是可以变成的最大的数。

首页