-
I am finding it hard to understand your code, why are you inputting bit twice ?? whats init ?? is that checking if array[0] and array[n-1] both have 1s ?what is place function doing ??
I really didn't get the record structure as well....
This is what I am trying to do:
- I am simply using the counting of 1s to get the first position of every run there is, then I will check if there is a possible run that wraps this, then I will remove the first run saved and last run saved, because I will be combining them now.
- after this, I simply take 2 heads and 2 tails(if more than 2 runs are there)
-If there is a tail that wraps it will be >=n and i will use modulus to make it normal..I think I am getting the positions of the runs right, I am having a bit trouble in the outputting part,
here's what I am doing:
- If my counts of runs contains only 1 element, meaning only 1 streak, I will check if the 1st tail of the run is greater than n if it is %, and then I will check if current(first pointer) is lying between the streak if it is cut the streak and find max between them, and min between this and k.
- If I have more than 1 streak, I will first check if any is getting greater than n, if %, then I will check if any is being cut by the current pointer, and then I will have 3 streaks,I will get maximum and minimum between k and print it...
Still getting wrong answer tho :(
-
If you don't "get" the Record struct then you simply don't know C++.
I don't "get" your alg, either!
Anyway, you sound a little upset.
Take a break.
Listen to a tune: Pojama People
-
Yes, maybe I don't know C++ ... but isn't what this forum is for, making others understand what you're trying to do, maybe I am a little frustrated and not thinking straight coz I have been banging my head over this for a week and now that I know I am very close,I am a little desperate... but if we simply said others that you didn't get this, you don't know c++..then its cool with me. anyways, I don't mean this in any disrespectful way, You have been kind enough to give your time for my problem and I am grateful..
-
You're upset, but don't put it on me. Just remember the golden rule: nobody cares.
-
never put it on you dude, instead thanked you. cool. good chat.
-
ulimit Man Page - Linux - SS64.com
Consider that the online checking tool may have specified a much lower memory budget for submitted programs.
Presumably with (perhaps) the intention of preventing brute-force algorithms which see fit to allocate large chunks of memory.
There may be nothing actually functionally wrong with your code, so long as the platform is willing to give you the memory you need.
But if the platform won't give you the memory, then segfault is what awaits you.
-
I am not getting segmentation error now, just the implementation is wrong still..some test cases are working perfectly while others giving wrong answer
-
What wrong results did you get, what input did you use?
Can you post the lastest code?
-
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;
}
-
TBH, you could do better with some functions to break up your 200+ line main.