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

The answer to the problem
Posted by [NKU]sweet 17 Sep 2010 15:10
we can easily design 1000 stacks using a linked list,every node we 'll use a int to store its data,another int to store its father's index,we'll use 8 byte each node, about 800K,that will get MLE.

Then we can see the index of a node's father will always <=100000,we can just use 17 bit to store it,instead of a int(32 bit),zipped it and get AC~ :)
Re: The answer to the problem
Posted by Vedernikoff Sergey (HSE: АОП) 17 Sep 2010 16:49
The problem can be solved much easier using only 101000 ints =) And complexity of the algo is about O (N logN)