Hi!
I was trying to solve this problem using this greedy strategy:
From an index i, we mark ans[i] = 1(initially all 0) and we loop till the end of the array and store the highest allowable difference in ones and zeroes, as well as the index for it. From this index, we begin our next cycle.
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
// short forms //
#define f first
#define s second
#define nl "\n"
#define pb push_back
#define all(x) x.begin(), x.end()
// debug //
#define pv(x) for(auto k : x){cout << k;} cout << nl;
#define pp(x) cout << x.f << " " << x.s << nl;
#define bv(x) if (x) cout << "true"; else cout << "false";
#define gp(x, y) x << " " << y
// loop //
#define fur(i, a, b) for(ll i = a; i <= b; i++)
#define ruf(i, a, b) for(ll i = a; i >= b; i--)
// pair //
typedef pair<ll, ll> pl;
// vector //
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pl> vp;
// constants //
const ll INF = 1e17;
const ll mod = 1e9 + 7;
const ll S = 1e5 + 5;
void solve(){
ll n, k;
cin >> n >> k;
vl a(n), ans(n, 0);
fur(i, 0, n-1){
char c; cin >> c;
a[i] = (ll)(c - '0');
}
//pv(a);
ll z, e;
fur(i, 0, n-1){
z = 0;
e = 0;
pl dif_i = {-1, -1};
ans[i] = 1;
ll j;
for(j = i; j < n; j++){
a[j] == 1? e++ : z++;
ll dif = abs(e - z);
if (dif >= dif_i.f && dif <= k)
dif_i = {dif, j};
}
i = dif_i.s;
}
pv(ans);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll t = 1;
cin >> t;
while(t--){
solve();
}
return 0;
}