← 返回题目列表

Codeforces · 1659/B

B. 位翻转

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

给你一个长度为 $$$n$$$ 的二进制字符串。您总共有 $$$k$$$ 步。在一次移动中,您必须选择一位。除该位外的所有位的状态都会翻转($$$0$$$ 变为 $$$1$$$,$$$1$$$ 变为 $$$0$$$)。您需要输出使用所有 $$$k$$$ 移动后可以获得的按字典顺序最大的字符串。另外,输出您将选择每个位的次数。如果有多种方法可以做到这一点,您可以输出其中任何一种。

二进制字符串 $$$a$$$ 按字典顺序大于相同长度的二进制字符串 $$$b$$$,当且仅当以下条件成立时:

- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 包含 $$$1$$$,字符串 $$$b$$$ 包含 $$$0$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例有两行。第一行有两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$0 \leq k \leq 10^9$$$)。

第二行有一个长度为 $$$n$$$ 的二进制字符串,每个字符要么是 $$$0$$$ 要么是 $$$1$$$。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出两行。

第一行应包含您可以获得的按字典顺序排列的最大字符串。

第二行应包含 $$$n$$$ 整数 $$$f_1, f_2, \ldots, f_n$$$,其中 $$$f_i$$$ 是选择第 $$$i$$$ 位的次数。所有整数的总和必须等于 $$$k$$$。

示例

输入 #1

6
6 3
100001
6 4
100011
6 0
000000
6 1
111001
6 11
101100
6 12
001110

输出 #1

111110
1 0 0 2 0 0 
111110
0 1 1 1 0 1 
000000
0 0 0 0 0 0 
100110
1 0 0 0 0 0 
111111
1 2 1 3 0 4 
111110
1 1 4 2 0 4

注意

这是第一个测试用例的解释。每个步骤都显示二进制字符串在移动过程中如何变化。

- 选择位$$$1$$$:$$$\color{red}{\underline{1}00001} \rightarrow \color{red}{\underline{1}}\color{blue}{11110}$$$。
- 选择位 $$$4$$$:$$$\color{red}{111\underline{1}10} \rightarrow \color{blue}{000}\color{red}{\underline{1}}\color{blue}{01}$$$。
- 选择位 $$$4$$$:$$$\color{red}{000\underline{1}01} \rightarrow \color{blue}{111}\color{red}{\underline{1}}\color{blue}{10}$$$。