Alternative Sufferings

general
1

Alternative Sufferings
You are given a binary string
S
S.

In one second, the following scenario happens simultaneously and independently for all the bits which are set to
1
1 in the string:

Change the bit from
1
1 to
0
0.
If the left neighbour exists and is
0
0, change it to
1
1.
If the right neighbour exists and is
0
0, change it to
1
1.
For example, if
S

010
S=010 initially, then after
1
1 second,
S

101
S=101 (the
1
1 bit and both its neighbours were changed). After another second,
S

010
S=010. Here, the first and the last bit were changed to
0
0 because earlier they were
1

  1. The middle bit was changed because it was
    0
    0 earlier and it was a neighbour of a
    1
    1 bit.

Find out the string
S
S after
K
K seconds.

Input Format
The first line of input will contain a single integer
T
T, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains two space-separated integers
N
N and
K
K — the length of string
S
S and the number of seconds.
The next line describes the string
S
S.
Output Format
For each test case, output the string
S
S after exactly
K
K seconds.

Constraints
1
≤
T
≤
1000
1≤T≤1000
1
≤
N
≤
1
0
5
1≤N≤10
5

1
≤
K
≤
1
0
9
1≤K≤10
9

The sum of
N
N over all test cases won’t exceed
1
0
6
10
6
.
S
S can only contain the characters
0
0 or
1
1.
Sample 1:
3
3 1
101
5 2
10001
14 3
10011010111000

Output
010
10101
01100101010101
Explanation:
Test case
1
1: The middle bit is changed to
1
1 since it had a neighbouring set bit (in this case both left and right) and both the set bits are changed to
0
0. Hence, after one second, it is
101
101.

Test case
2
2: After first second, the string
S
S will be
01010
01010. After another second , the string becomes
10101
10101.

include <bits/stdc++.h>
define ll long long
define pb push_back
define cy cout << “YES\n”
define cn cout << “NO\n”
define c1 cout << “-1\n”
define all(x) x.begin(), x.end()
define re(x) x.rbegin(), x.rend()
define F first
define S second
define ii pair<ll, ll>
define IOS
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
using namespace std;

int main()
{
IOS
ll t;
cin >> t;
while (t–)
{
ll n, k;
cin >> n >> k;

    string s;
    cin >> s;

    string ans = s, prev = s;
    ll mk = 0;

    while (mk != n)
    {
        // cout << ans << endl;

        string temp = ans;
        ll cnt = 0;
        for (ll i = 0; i < n; i++)
        {
            if (ans[i] == '1')
            {
                temp[i] = '0';
                cnt++;
            }
            else if (ans[i] == '0')
            {
                if (i > 0 && ans[i - 1] == '1')
                {
                    temp[i] = '1';
                    cnt++;
                }
                else if (i < n - 1 && ans[i + 1] == '1')
                {
                    temp[i] = '1';
                    cnt++;
                }
            }
        }

        if (ans == prev && mk > 0)
            break;
        if (mk % 2 == 0)
        {
            prev = ans;
        }
        ans = temp;
        mk++;
        if (mk == k)
            break;
    }

    if (mk % 2 != k % 2)
    {
        string temp = ans;

        for (ll i = 0; i < n; i++)
        {
            if (ans[i] == '1')
            {
                temp[i] = '0';
            }
            if (ans[i] == '0')
            {
                if (i > 0 && ans[i - 1] == '1')
                {
                    temp[i] = '1';
                }
                if (i < n - 1 && ans[i + 1] == '1')
                {
                    temp[i] = '1';
                }
            }
        }

        ans = temp;
    }
    cout << ans << endl;
}
return 0;

}