ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1220. Stacks

Where is logic?
Послано Alex Mullabaev'` 10 фев 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][0] = 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][0] = 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?