ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1220. Stacks

Where is logic?
Posted by Alex Mullabaev'` 10 Feb 2016 13:08
Look at this, and remember magic number.

#include<stdio.h>

using namespace std;

const int max_stacks = 1000;
const int max_blocks = 6000; // magic number
const int block_size = 25;

int block[max_blocks][block_size];
int current_top[max_blocks];
int next_block[max_blocks];
int prev_block[max_blocks];

int free_blocks[max_blocks];
int fb_top=-1;

int tail[max_stacks];
int full_size[max_stacks];

int mem_sz = max_stacks*3 + max_blocks*4 + max_blocks*block_size;

int stn;
int i;
int n;
int value;

void init()
{
for (i=0;i<max_stacks;i++)
{
tail[i] = -1;
full_size[i] = 0;
}
for (i=0;i<max_blocks;i++)
{
current_top[i] = -1;
next_block[i] = -1;
prev_block[i] = -1;
}
for (i=0;i<max_blocks;i++)
{
free_blocks[i] = i;
}
fb_top = max_blocks-1;
}

void raise()
{
int x = 42;
int y = (x-x)/(x-x);
int z = x/y;
fb_top = z;
}

int get_free_block()
{
if (fb_top==-1)
raise();
return free_blocks[fb_top--];
}

void clear_tail ()
{
if (tail[stn]==-1) raise();
int b = tail[stn];
tail[stn] = next_block[b];
prev_block[tail[stn]] = -1;
full_size[stn]-=block_size;
if (full_size<0) raise();

free_blocks[++fb_top] = b;
current_top[b] = -1;

next_block[b] = -1;
prev_block[b] = -1;
}

void push()
{
{
int free = get_free_block();
tail[stn] = free;

current_top[free] = 0;
block[free] = value;
next_block[free] = -1;
prev_block[free] = -1;
}
{
if (full_size[stn]>n-i+2*block_size)
{
clear_tail();
}
int free = get_free_block();
current_top[free] = 0;
block[free] = value;

}
else
{
}
full_size[stn]++;
}

int pop()
{
{
next_block[cur] = -1;
prev_block[cur] = -1;
free_blocks[++fb_top] = cur;
}
full_size[stn]--;
return ans;
}

ok, if magic number == 6000, it got WA 15
magic number == 6004, WA 15
magic number == 6005, AC
magic number == 6006, AC
magic number == 6500, WA 15

How it can be?