Bit Flipping (Codeforces 1659B)
Tags: Greedy, bitmasks

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.A binary string $$$a$$$ is lexicographically larger than a binary string $$$b$$$ of the same length, if and only if the following holds:   in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ contains a $$$1$$$, and the string $$$b$$$ contains a $$$0$$$. 

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$)  — the number of test cases.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$$$).The second line has a binary string of length $$$n$$$, each character is either $$$0$$$ or $$$1$$$.The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output two lines.The first line should contain the lexicographically largest string you can obtain.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$$$.

Note: Here is the explanation for the first testcase. Each step shows how the binary string changes in a move.  Choose bit $$$1$$$: $$$\color{red}{\underline{1}00001} \rightarrow \color{red}{\underline{1}}\color{blue}{11110}$$$.  Choose bit $$$4$$$: $$$\color{red}{111\underline{1}10} \rightarrow \color{blue}{000}\color{red}{\underline{1}}\color{blue}{01}$$$.  Choose bit $$$4$$$: $$$\color{red}{000\underline{1}01} \rightarrow \color{blue}{111}\color{red}{\underline{1}}\color{blue}{10}$$$.  The final string is $$$111110$$$ and this is the lexicographically largest string we can get.

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

Sample Outputs:
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

Solution (Python):
import sys

def solve():
    inp = sys.stdin.readline
    (n, k) = map(int, inp().split())
    s = list(inp())
    s.pop()
    r = [0] * n
    k_bak = k
    if k % 2 == 0:
        for i in range(0, n - 1):
            if s[i] == '0' and k > 0:
                s[i] = '1'
                r[i] = 1
                k -= 1
        r[-1] = k
        if (k_bak - k) % 2:
            s[-1] = str(int(s[-1]) ^ 1)
    else:
        for i in range(0, n - 1):
            if s[i] == '1' and k > 0:
                s[i] = '1'
                r[i] = 1
                k -= 1
            elif s[i] == '1':
                s[i] = '0'
            else:
                s[i] = '1'
        r[-1] = k
        if (k_bak - k) % 2:
            s[-1] = str(int(s[-1]) ^ 1)
    print(''.join(s))
    print(' '.join(map(str, r)))

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    (n, k) = map(int, input().split())
    b = str(input())
    ans = [0] * n
    if k & 1:
        for (idx, char) in enumerate(b):
            if not k:
                b = list(map(int, b))
                b = list(map(lambda x: x ^ 1, b))
                b = list(map(str, b))
                print('1' * idx + ''.join(b[idx:]))
                print(' '.join(map(str, ans)))
                return
            if char == '1':
                ans[idx] += 1
                k -= 1
    else:
        for (idx, char) in enumerate(b):
            if not k:
                print('1' * idx + b[idx:])
                print(' '.join(map(str, ans)))
                return
            if char == '0':
                ans[idx] += 1
                k -= 1
    ans[-1] += k
    if not k & 1:
        print('1' * n)
    else:
        print('1' * (n - 1) + '0')
    print(' '.join(map(str, ans)))
for i in range(int(input())):
    solve()

Solution (Python):
def binary(l, n, k):
    if k % 2 == 1:
        odd(l, n, k)
    if k % 2 == 0:
        even(l, n, k)

def odd(list, n, k):
    for i in range(n):
        if list[i] == '1' and k > 0:
            list[i] = '0'
            count[i] += 1
            k -= 1
        if list[i] == '0':
            list[i] = '1'
        else:
            list[i] = '0'
    if k > 0:
        count[-1] += k
        if k % 2 != 0:
            if list[-1] == '0':
                list[-1] = '1'
            else:
                list[-1] = '0'

def even(list, n, k):
    for i in range(n):
        if list[i] == '0' and k > 0:
            list[i] = '1'
            count[i] += 1
            k -= 1
    if k > 0:
        count[-1] += k
        if k % 2 != 0:
            if list[-1] == '0':
                list[-1] = '1'
            else:
                list[-1] = '0'
if __name__ == '__main__':
    t = int(input())
    n_list = []
    k_list = []
    binary_string_list = []
    for i in range(t):
        temp = input().split()
        n_list.append(int(temp[0]))
        k_list.append(int(temp[1]))
        binary_string_list.append(list(input()))
    for i in range(t):
        count = [0] * n_list[i]
        binary(binary_string_list[i], n_list[i], k_list[i])
        print(''.join(binary_string_list[i]))
        print(' '.join(('%s' % i for i in count)))