Break the string(INOI 2021) Wrong Answer

1

I was solving the following problem https://www.codechef.com/INOIPRAC/problems/BREAKSTR.

Here is my code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const ll INF = 1e15;
const ll MOD = 1e9+7;
ll total_count;
string final_ans;
// string one -  count of ones in the final string
// string zero - count of zeroes in the final string
// count_zero - count of zeroes in the input string
// count_one - count of ones in the input string
// final_ans - the final string which is the answer
void solve(int i,int n,int k,string&s,int string_one,int string_zero,string ans,int count_zero,int count_one){
	if(i>=s.size()){
		if(string_one<total_count){
			total_count = string_one;
			final_ans = ans;
		}
		return;
	}
	count_one+= (s[i]=='1');
	count_zero+=(s[i]=='0');
	if(abs(count_one-count_zero)<=k)
		solve(i+1,n,k,s,string_one,string_zero+1,ans+"0",count_zero,count_one);
	solve(i+1,n,k,s,string_one+1,string_zero,ans+"1",(s[i]=='0'),(s[i]=='1'));
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		total_count = INF;
		final_ans = "";
		int n,k;
		cin>>n>>k;
		string s;
		cin>>s;
		string ans;
		int string_one = 0,string_zero = 0,count_zero = 0,count_one= 0;
		ans+="1";
		if(s[0]=='0')
			count_zero++;
		else
			count_one++;
		solve(1,n,k,s,1,string_zero,ans,count_zero,count_one);
		cout<<final_ans<<"\n";
	}
}

I know my code is messy and is not the optimal solution. But it is still giving me wrong answer on the last two cases of the first subtask(where length of the string <=20).
Can anyone tell me where my code is going wrong?

1 Like