can't see whtats the wrong output, online site doesn't show that, just correct or wrong, some of my test cases passes but some don't:
Algo:
Look for two longest streaks of 1s, for rotation keep a pointer(current) and look how much of both of these streaks is being shown, if breaked then divide in two parts and see which is max, the max one is then seen with k, if greater than k then print k, else print max..
Code:
#include <iostream>
#include <cmath>
#include <algorithm>
#include <limits>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <time.h>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <list>
#include <iterator>
#include <iosfwd>
using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::map;
using std::max;
using std::min;
const int MAX=1e5+5;
int start_ind_count_ones[MAX];
bool compa(int a,int b)
{
if(a>b) return true;
return false;
}
int main(){
int n,q,k;cin>>n>>q>>k; //n->number of elements in input_arrayay,q->number of queries, k->maximum consecutive ones there could be
vector<int> input_array(n); //input_arrayay for storing numbers
int count_no_of_zero=0;
for(int i=0;i<n;i++) {cin>>input_array[i];if(input_array[i]==0) count_no_of_zero++;} //elements only of form 1 or 0
string query_string;cin>>query_string; //query_stringy string which contains only '?' and '!'
if(count_no_of_zero==n) //if all 0s print 0s
{
for(int i=0;i<q;i++)
{
if(query_string[i]=='?')
cout<<"0\n";
}
return 0;
}
else if(count_no_of_zero==0) //If all are 1s then print minimum of n-1 or k
{
for(int i=0;i<q;i++)
{
if(query_string[i]=='?')
cout<<min(n,k)<<"\n";
}
return 0;
}
int head_of_1_long_streak=0,tail_of_1_long_streak=0,head_of_2_long_streak=0,tail_of_2_long_streak=0;
//stores the place where each run of 1's start
vector<int> temp_ones;//stores the count of ones and then sort this to get head and tails..
for(int i=0;i<n;)
{
int c=0;int temp_head=0;int flag=0;
while(i<n && input_array[i]==1)
{
if(flag==0) {temp_head=i;flag=1;} //flag needed to secure head of the run
c++;i++;
}
if(temp_head<n)
{start_ind_count_ones[temp_head]=c;
if(c!=0)
temp_ones.push_back(c);}
i++;
}
vector<int> new_temp;
if(temp_ones.size()!=1 && input_array[0]==1 && input_array[n-1]==1) //if array is like [1,....,1]
{
int x,y;
x=temp_ones[0];y=temp_ones[temp_ones.size()-1];
vector<int> extra(temp_ones.begin()+1,temp_ones.end()-1); //this is done so that if we have [1,1,0,1,1,1] then we only see one streak of 1s i.e from 3 till 7(here 7 means 1, since this wraps the array)
new_temp=extra;
new_temp.push_back(x+y);//push the wrapped length(or count of ones with wrapped 1s)
for(int i=n-1;i>=0;i--)
{
if(start_ind_count_ones[i]!=0)
{start_ind_count_ones[i]=new_temp[new_temp.size()-1];break;}
}
}
sort(new_temp.begin(),new_temp.end(),compa); //sort in decreasing order
for(int i=0;i<n;i++)
{
if(start_ind_count_ones[i]==new_temp[0]) // HERE WE will see new_temp[0] contains the longest runs of 1, so we will match this with the array that stored the first index of all the runs
{
head_of_1_long_streak=i;
tail_of_1_long_streak=start_ind_count_ones[i]+i-1; //if run is wrapped we will see tail of run as >=n later we will use mod
}
else if( new_temp.size()>=2 && start_ind_count_ones[i]==new_temp[1]) //do same for 2nd longest
{
head_of_2_long_streak=i;
tail_of_2_long_streak=start_ind_count_ones[i]+i-1;
}
}
// cout<<head_of_1_long_streak<<" "<<tail_of_1_long_streak<<" "<<head_of_2_long_streak<<" "<<tail_of_2_long_streak<<"\n";
int current=0;// "first" pointer
for(int i=0;i<q;i++)
{
if(query_string[i]=='!') //query for rotation we can simply move the pointer which shows the first element
{
current--;
if(current<0)
current=n-1;
}
else
{
if(new_temp.size()==1) //IF there is only 1 longest run of ones
{
if(tail_of_1_long_streak>=n)//wrapped 1s
{
int temp_tail=tail_of_1_long_streak%n;
if(current<=temp_tail) // if the current is in between wrapped ones in the begining
{
int max_1=temp_tail-current+1;
int max_2=new_temp[0]-max_1;
cout<<min(max(max_1,max_2),k)<<"\n";
}
else if(current>=head_of_1_long_streak) //if the current is in between wrapped ones in the end
{
int max_11=current-head_of_1_long_streak+1;
int max_12=new_temp[0]-max_11;
cout<<min(max(max_11,max_12),k)<<"\n";
}
else //this is the case if current doesn't cut the streak of ones
{
cout<<min(new_temp[0],k)<<"\n";
}
}
else //If we don't have a wrapped ones case then simple breaking of streak
{
if(current<=tail_of_1_long_streak && current>=head_of_1_long_streak)
{
int max_1a=tail_of_1_long_streak-current+1;
int max_2a=new_temp[0]-max_1a;
cout<<min(max(max_1a,max_2a),k)<<"\n";
}
else
cout<<min(new_temp[0],k)<<"\n";
}
}
else //case for 2 longest streaks
{
int new_tail=tail_of_1_long_streak;int new_temp_tail=tail_of_2_long_streak;
if(tail_of_1_long_streak>=n)
{
new_tail=tail_of_1_long_streak%n;
}
else if(tail_of_2_long_streak>=n)
{
new_temp_tail=tail_of_2_long_streak%n;
}
int max1=new_temp[0];int max2=new_temp[1];
int max11=0;int max22=0;
if(current<=new_tail && (tail_of_1_long_streak!=new_tail || current>=head_of_1_long_streak))
{
max1=new_tail-current+1;
max11=new_temp[0]-max1;
}
else if(current>=head_of_1_long_streak && tail_of_1_long_streak!=new_tail)
{
max1=current-head_of_1_long_streak+1;
max11=new_temp[0]-max1;
}
else if(current<=new_temp_tail && (tail_of_2_long_streak!=new_temp_tail || current>=head_of_2_long_streak))
{
max2=new_temp_tail-current+1;
max22=new_temp[1]-max2;
}
else if(current>=head_of_2_long_streak && tail_of_2_long_streak!=new_temp_tail)
{
max2=current-head_of_1_long_streak+1;
max22=new_temp[1]-max2;
}
// cout<<max1<<" "<<max11<<"\n";
cout<<min(max(max(max1,max11),max(max2,max22)),k)<<"\n";
}
}
}
//cout<<query_string.length()<<"\n";
//cout<<tick()<<"\n";
return 0;
}
