← 返回题目列表

AtCoder · abc380_c

F. 移动段

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

分数: 300 点

问题陈述

给你一个字符串 S 长度 N 组成 0 和 1.
移动 K-th 1-从头开始的块 S 紧接在 (K-1)-th 1- 块,并打印结果字符串。

保证 S 至少包含 K 1- 块。

这是更准确的描述。

  • 让 S_{l\ldots r} 表示子串 S 来自 l- 第一个字符 r- 第一个字符。
  • 我们定义一个子字符串 S_{l\ldots r} of S 成为 1- 如果满足以下所有条件则阻止:
    • S_l = S_{l+1} = \cdots = S_r = 1
    • l = 1 or S_{l-1} = 0
    • r = N or S_{r+1} = 0
  • 假设所有 1- 中的块 S 是 S_{l_1\ldots r_1}, \ldots, S_{l_m\ldots r_m},其中 l_1 < l_2 < \cdots < l_m.

    然后,我们定义长度 N 字符串 T,通过移动获得 K-th 1- 紧接在 (K-1)-th 1- 块,如下:

    • T_i = S_i 为 1 \leq i \leq r_{K-1}
    • T_i = 1 为 r_{K-1} + 1 \leq i \leq r_{K-1} + (r_K - l_K) + 1
    • T_i = 0 为 r_{K-1} + (r_K - l_K) + 2 \leq i \leq r_K
    • T_i = S_i 为 r_K + 1 \leq i \leq N

约束

  • 1 \leq N \leq 5 \times 10^5
  • S 是一个长度为的字符串 N 组成 0 和 1.
  • 2 \leq K
  • S 至少包含 K 1- 块。

输入

输入由标准输入按以下格式给出:

N K
S

输出

打印答案。


示例输入 1

15 3
010011100011001

示例输出 1

010011111000001

S 有四个 1- 块:从第 2 个到第 2 个字符、从第 5 个到第 7 个字符、从第 11 个到第 12 个字符、从第 15 个到第 15 个字符。


示例输入 2

10 2
1011111111

示例输出 2

1111111110