ENG  RUSTimus 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

Yet another way to solve
Posted by melkiy 20 Oct 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