Can anybody tell what is the issue in this, did pass a lot of cases but crashed for a case
The problem
https://mirror.codeforces.com/contest/1884/problem/B
// This is going to be the template for competitive programming
include // cin, cout, basic I/O
include // sort, max, min, lower_bound, upper_bound
include // sqrt, pow, abs, log, sin, cos, etc.
include // memset, memcpy, strcmp (C-style strings)
include // vector
include // set, multiset, ordered sets
include // map, multimap
include // hash map (average O(1))
include // hash set (average O(1))
include // queue, priority_queue
include // stack
include // deque (double-ended queue)
include // bitset (fixed-size bit manipulation)
include // accumulate, gcd, lcm, iota`
include // INT_MAX, LLONG_MIN, etc.
include // assert for debugging
define en '\n'
define ll long long
define MOD 1000000007
using namespace std; void fast_io() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); } /*#include <ext/pb_ds/assoc_container.hpp>
include <ext/pb_ds/tree_policy.hpp>
typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;
*/ // read question properly // don't forget newlines!!!!!! // take care about cin >> t; // comment the optimization before debugging // ALWAYS USE FIXED << SETPRECISION WHILE OUTPUTTING FLOATS // BAKCHODI MAT KAR LAUDE
// g++ filename -o a then ./a g++ fightingtournament1400.cpp -o a
/* Dry run
a.erase(unique(a.begin(), a.end()), a.end()); used to remove duplicate elements from a sorted vectpor
a<=b<=c
ai+aj>0
1001110000 101111
1010110000101011 0101001234343433
1122344444556678 0112223456677888
so is it the dist of first 1 from the first place where all 1 will come + no of 1 -1 less than that posn?
1 3 8 */
void dowork(ll int n, string s){ ll int i=0;
reverse(s.begin(),s.end()); ll int cnt=0; vectorans(n,0); vectorones(n,0); if(s[0]=='1'){ ones[0]++; } for(i=1;i<n;i++){ if(s[i]=='1'){ ones[i]=ones[i-1]+1; } else{ ones[i]=ones[i-1]; } }
// for(auto it:ones){ // cout<<it<<" "; // } // cout<<en;
i=0; vectorzero(n,0); vectorzeroes; if(s[0]=='0'){ zero[0]++; zeroes.push_back(i); } for(i=1;i<n;i++){ if(s[i]=='0'){ zero[i]=zero[i-1]+1; zeroes.push_back(i); } else{ zero[i]=zero[i-1]; } }
// for(auto it:zeroes){ // cout<<it<<" "; // } // cout<<en; // for(auto it:zero){ // cout<<it<<" "; // } // cout<<en;
if(zeroes.size()==0){ for(i=0;i<n;i++){ cout<<-1<<" "; } cout<<en; return; }
vectorprefix(zeroes.size(),0); prefix[0]=zeroes[0]; for(i=1;i<prefix.size();i++){ prefix[i]=prefix[i-1]+zeroes[i]; }
// for(auto it:prefix){ // cout<<it<<" "; // } // cout<<en; ll int j=0;
vectorfinal(n,0); for(i=0;i<n;i++){ if(i==0 && prefix[j]==0){ final[i]=0; j++; } else if(i==0 && prefix[j]!=0){ final[i]=0; } else if(j<prefix.size() && i==zeroes[j]){ final[i]=prefix[j]; j++; } else{ final[i]=final[i-1]; } }
// for(auto it:final){ // cout<<it<<" "; // } // cout<<en;
j=0;
vectoronepos;
for(i=0;i<n;i++){ if(s[i]=='1'){ onepos.push_back(i); } }
// for(auto it:onepos){ // cout<<it<<" "; // } // cout<<en;
vector onepref(onepos.size(),0); if(onepref.size()==0){ for(i=0;i<n;i++){ cout<<0<<" "; } cout<<en; return;
}
if(!onepos.empty()){ onepref[0]=onepos[0]; } for(i=1;i<onepos.size();i++){ onepref[i]=onepref[i-1]+onepos[i]; }
// for(auto it:onepref){
// cout<<it<<" ";
// }
// cout<<en;j=0; vectoronn(n,0); for(i=0;i<n;i++){
if(i==0 && onepos[j]==0){
onn[i]=0;
j++;
}
else if(i==0 && onepos[j]!=0){
onn[i]=0;
}
else if(j<onepos.size() && i==onepos[j]){
onn[i]=onepref[j];
j++;
}
else{onn[i]=onn[i-1]; } }
// for(auto it:onn){ // cout<<it<<" "; // } // cout<<en; j=0; for(i=1;i<n;i++){ ll before = zero[i-1]; ll z = ones[i-1];
if(z==0){ ans[j]=0; j++; continue; } ll o = lower_bound( zero.begin()+i, zero.end(), before + z ) — zero.begin();
if(j<n && o!=n){
ll int u=final[o]-final[i-1];
ll int k=onn[i-1];
ans[j]=u-k;
j++;
}
else{
break;
}}
while(j<n){ ans[j]=-1; j++; } for(auto it:ans){ cout<<it<<" "; } cout<<en; return;
}
int main(){ fast_io(); int t; cin>>t; ll int j=0; while(j<t){ ll int n; cin>>n; string s; cin>>s; /* if(j==0){ cout<<n<<"_"; for(int i=0;i<n;i++){ cout<<arr[i]<<"_"; }
}*/
dowork(n,s);
j++;
}
return 0;}
