F - Move Segment Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

0, 1 のみからなる長さ N の文字列 S が与えられます。
S の中で先頭から K 番目の 1 の塊を K-1 番目の 1 の塊の直後まで移動した文字列を出力してください。

なお、S には 1 の塊が K 個以上含まれることが保証されます。

より正確な説明は以下の通りです。

  • S の l 文字目から r 文字目までからなる部分文字列を S_{l\ldots r} と表す。
  • S の部分文字列 S_{l\ldots r} が 1 の塊であるとは、以下の条件を全て満たすことと定める。
    • S_l=S_{l+1}=\cdots=S_r= 1
    • l=1 または S_{l-1}= 0
    • r=N または S_{r+1}= 0
  • S に含まれる 1 の塊が S_{l_1\ldots r_1},\ldots,S_{l_m\ldots r_m} で全てであり、l_1 < \cdots < l_m を満たしているとする。
    このとき、以下で定義される長さ N の文字列 T を、「S の中で先頭から K 番目の 1 の塊を K-1 番目の 1 の塊の直後まで移動した文字列」と定める
    • 1 \leq i \leq r_{K-1} のとき T_i = S_i
    • r_{K-1}+1 \leq i \leq r_{K-1}+(r_K-l_K)+1 のとき T_i= 1
    • r_{K-1}+(r_K-l_K)+2 \leq i \leq r_K のとき T_i= 0
    • r_K+1 \leq i \leq N のとき T_i=S_i

制約

  • 1 \leq N \leq 5\times 10^5
  • S は 0, 1 のみからなる長さ N の文字列
  • 2 \leq K
  • S には 1 の塊が K 個以上含まれる

入力

入力は以下の形式で標準入力から与えられる。

N K
S

出力

答えを出力せよ。

入力例 1

15 3
010011100011001

出力例 1

010011111000001

S には、2 文字目から 2 文字目、5 文字目から 7 文字目、11 文字目から 12 文字目、15 文字目から 15 文字目の 4 つの 1 の塊があります。

入力例 2

10 2
1011111111

出力例 2

1111111110

Score : 300 points

Problem Statement

You are given a string S of length N consisting of 0 and 1.
Move the K-th 1-block from the beginning in S to immediately after the (K-1)-th 1-block, and print the resulting string.

It is guaranteed that S contains at least K 1-blocks.

Here is a more precise description.

  • Let S_{l\ldots r} denote the substring of S from the l-th character through the r-th character.
  • We define a substring S_{l\ldots r} of S to be a 1-block if it satisfies all of the following conditions:
    • S_l = S_{l+1} = \cdots = S_r = 1
    • l = 1 or S_{l-1} = 0
    • r = N or S_{r+1} = 0

  • Suppose that all 1-blocks in S are S_{l_1\ldots r_1}, \ldots, S_{l_m\ldots r_m}, where l_1 < l_2 < \cdots < l_m.

    Then, we define the length N string T, obtained by moving the K-th 1-block to immediately after the (K-1)-th 1-block, as follows:

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

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • S is a string of length N consisting of 0 and 1.
  • 2 \leq K
  • S contains at least K 1-blocks.

Input

The input is given from Standard Input in the following format:

N K
S

Output

Print the answer.

Sample Input 1

15 3
010011100011001

Sample Output 1

010011111000001

S has four 1-blocks: from the 2nd to the 2nd character, from the 5th to the 7th character, from the 11th to the 12th character, and from the 15th to the 15th character.

Sample Input 2

10 2
1011111111

Sample Output 2

1111111110