I solve this problem about half of year.
I use Binary Heap to store n/2+2 elemets at first.
If you have WA 6-8 try to check your Binary Heap in some random tests with odd and even N (10 or 11)
My wrong Binary Heap work different in other order of elements :)
For example
10
1 2 3 4 5 6 7 8 9 10

10
10 9 8 7 6 5 4 3 2 1

10
1 6 8 3 9 5 2 10 4 7

Answers are 5.5

11
1 2 3 4 5 6 7 8 9 10 11

11
11 10 9 8 7 6 5 4 3 2 1

11
11 10 3 8 9 7 6 2 1 5 4

Answers are 6.0

P.S: Escape integer overflow :)

Edited by author 09.10.2009 02:56

Data structure you used is called "binary heap", not "pyramide" =)

Thank you! I got AC:)
Very very usefull hint!

Yep, another hint:

Make array int a[250 000/4*3 + 2]

Get numbers from 1 to min ( n, 250 000/4*3 + 2 )

Sort ( a, a + 250 000/4*3 + 2 )

Get the rest numbers from 250 000/4*3 + 2 + 1 to n in positions 125001 (counting from 0) .. till the end. Make sure they will fit. :)
It's so because we have to read at most 250 000 / 4 numbers. :)

Then sort again.

That's the first 125001 numbers of your array.
Output the answer.

125 ms
868 KB
http://acm.timus.ru/status.aspx?space=1&num=1306&from=3146166&count=1

Edited by author 26.08.2010 15:25