ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
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 head[max_stacks];
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++)
{
head[i] = -1;
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()
{
if (head[stn]==-1)
{
int free = get_free_block();
head[stn] = free;
tail[stn] = free;

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

next_block[head[stn]] = free;
prev_block[free] = head[stn];
head[stn] = free;
}
else
{
block[head[stn]][++current_top[head[stn]]] = value;
}
full_size[stn]++;
}

int pop()
{
if (current_top[head[stn]]==-1) raise;
int ans = block[head[stn]][current_top[head[stn]]--];
if (current_top[head[stn]]==-1)
{
int cur = head[stn];
head[stn] = prev_block[head[stn]];
next_block[head[stn]]=-1;
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?