HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppModerate

Aliens at the train

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
thealienstrain

Problem

I solved this problem on SPOJ:


The aliens have arrived to Earth and everything is in harmony, the two
races can live together. However, one specific Female Alien does not
want to see humans on her way to the university, the alien must use
the train as every human does. But she can choose any train station
such she doesn't see more than \$B\$ humans, however, the Alien wants
to go as far as possible with the train. Please, help her in this
task.


INPUT:


You will receive one integer \$T\$ denoting the number of
test cases, then, the next line will contain two integers \$A_t\$
\$B_t\$ where \$A_t\$ and \$B_t\$ is the number of stations in the
train (\$1\leq A_t \leq100,000\$) and the number of people that the
alien wants to see as maximum (\$1\leq B_t \leq10,000,000\$), after
that, one line containing \$A_t\$ integers separated by a single space
will denote the number of people the Alien can find in the \$A_t(i)\$
station. (For each station there will be as much 100 people.)


OUTPUT:


Your output should consist on \$T\$ pair of numbers denoting
the number of people the alien will see and the number of stations she
will pass respectively.


EXAMPLE Input / Output:


INPUT:

1
5 100
20 15 30 80 100



OUTPUT

65 3


My solution was just on the border of the time limit. I want to know of any improvements for my code in the context of competitive programming and the C/C++ languages.

How can I speed up the I/O and how can I shorten my code?

`#include
#include
using namespace std;

int main()
{
int t,siz;
scanf("%d",&t);
long long int at,bt,sum=0,max=0,maxsum=0,peep=0;
deque people;
while(t--){
sum=max=maxsum=peep=0;
people.clear();
scanf("%lld%lld",&at,&bt);
while(at--){
scanf("%lld",&peep);
people.push_back(peep);
if(sum+peepbt){
sum-=people.front();
people.pop_front();

Solution

You're likely to be correct that the main performance bottleneck is I/O in this program. For that reason, you might consider doing one or more of the following:

Read a line at a time

Try using fgets to fetch a line at a time and then use sscanf to parse the numbers from the buffer. This may be particularly useful for reading the train station line.

Roll your own scanf replacement

The scanf function is useful but general purpose. A faster special purpose sscanf replacement function which also does very little error checking, would be this:

const char *fetchnum(const char *buffer, long long int *n)
{
    for (*n = 0; *buffer >= '0' && *buffer <= '9'; buffer++) 
        *n = 10 * (*n) + (long long int)(*buffer - '0');
    return ++buffer;
}


Consider doing lower level I/O

Right now, your code uses the relatively high level scanf function, but you might find a performance gain using lower level calls such as read and then parsing the lines in memory.

Code Snippets

const char *fetchnum(const char *buffer, long long int *n)
{
    for (*n = 0; *buffer >= '0' && *buffer <= '9'; buffer++) 
        *n = 10 * (*n) + (long long int)(*buffer - '0');
    return ++buffer;
}

Context

StackExchange Code Review Q#59486, answer score: 15

Revisions (0)

No revisions yet.