1659B.md (2386B)
1 Source: https://codeforces.com/problemset/problem/1659/B 2 3 B. Bit Flipping 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a binary string of length $n$. You have exactly $k$ moves. In one move, you must select a single bit. The state of all bits except that bit will get flipped ($0$ becomes $1$, $1$ becomes $0$). You need to output the lexicographically largest string that you can get after using all $k$ moves. Also, output the number of times you will select each bit. If there are multiple ways to do this, you may output any of them. 22 23 A binary string $a$ is lexicographically larger than a binary string $b$ of the same length, if and only if the following holds: 24 25 * in the first position where $a$ and $b$ differ, the string $a$ contains a $1$, and the string $b$ contains a $0$. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. 30 31 Each test case has two lines. The first line has two integers $n$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$; $0 \leq k \leq 10^9$). 32 33 The second line has a binary string of length $n$, each character is either $0$ or $1$. 34 35 The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 36 37 Output 38 39 For each test case, output two lines. 40 41 The first line should contain the lexicographically largest string you can obtain. 42 43 The second line should contain $n$ integers $f_1, f_2, \ldots, f_n$, where $f_i$ is the number of times the $i$-th bit is selected. The sum of all the integers must be equal to $k$. 44 45 Example 46 47 Input 48 49 ``` 50 6 51 52 6 3 53 54 100001 55 56 6 4 57 58 100011 59 60 6 0 61 62 000000 63 64 6 1 65 66 111001 67 68 6 11 69 70 101100 71 72 6 12 73 74 001110 75 ``` 76 77 Output 78 79 ``` 80 111110 81 1 0 0 2 0 0 82 111110 83 0 1 1 1 0 1 84 000000 85 0 0 0 0 0 0 86 100110 87 1 0 0 0 0 0 88 111111 89 1 2 1 3 0 4 90 111110 91 1 1 4 2 0 4 92 ``` 93 94 Note 95 96 Here is the explanation for the first testcase. Each step shows how the binary string changes in a move. 97 98 * Choose bit $1$: $\color{red}{\underline{1}00001} \rightarrow \color{red}{\underline{1}}\color{blue}{11110}$. 99 * Choose bit $4$: $\color{red}{111\underline{1}10} \rightarrow \color{blue}{000}\color{red}{\underline{1}}\color{blue}{01}$. 100 * Choose bit $4$: $\color{red}{000\underline{1}01} \rightarrow \color{blue}{111}\color{red}{\underline{1}}\color{blue}{10}$. 101 102 The final string is $111110$ and this is the lexicographically largest string we can get.