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

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

Yet another way to solve
Послано melkiy 20 окт 2010 06:45
It seems someone have suggested to hold a common memory segment for all stacks. Here is my way to solve with some details.

Allocate a large array - a common segment for all stacks, and define the size of a block.
int a[BLOCKS*BLOCK_SIZE];
Each block stores (BLOCK_SIZE-1) cells for the numbers and one cells to link it with the previous block for the stack.

Also it is useful to have a bit map reflecting if a particular block is occupied. Make functions find_free_block and release_block.
Also i was needed a couple of arrays of int[1000].

When the next stack grows above (BLOCK_SIZE-1)*k, the new block is occupied and the stack's memory becomes BLOCK_SIZE*(k+1). On the other hand, when i can release a block after POP i do this for memory reuse.

It was found experimetally at the price of 5 MLE attempts that acceptable parameters are:
BLOCKS = 3200; //number of blocks
BLOCK_SIZE = 50; //integers, not bytes