...and without re-reading input. O(N*logN) sometimes faster then O(N) ;-) Nice problem.

Edited by author 02.04.2004 15:27

could you please open up your secret? at leaest a bit? many people are worried about it:)))

I guess you confused me with the very best man who solved this  problem in N/2 memory. Sorry, I'm just Ilya Teterin from contest.ur.ru forum :), so I'm interested in the "secret" too ;)

Use a data structure of Heap
Heap can help you insert in O(logn) and "pop" the biggest/smallest item in O(logn), and to realise it you need only a array.
With "Heap" we can solve this problem so easily. Read half of the data from the input, and then read one, pop biggest/smallest one, you can find at last pop one/two time(s), the midest number is found!!

hay, can you send solution to email mathit@mail.ru
;->

Edited by author 02.01.2006 17:04

I made "gcc median2.cpp -o median2.cpp" yesterday ;) If you familiar with GNU C compiler you will understand...

i got AC time=0.14 !!