I get AC using priority_queue<unsigned int>
At first I push n/2+1 numbers then I read next number,push it to queue,pop biggest element until I have elements
If n odd I use 1 top elem for answer
else
I use 2 top elements for answer such way:
if (top1+top2) mod 2=0 I output top1/2+top2/2+top1 mod 2 and then print ".0"
else I output top1/2+top2/2 and then print ".5"
I hope it'll help somebody.
P.S thank to authors of this problem.I like this problem very much!


Edited by author 07.02.2008 01:49

CHIDEMYAN SERGEY, thanks a lot! You helped me very much. Finally, I passed it!

Edited by author 21.03.2012 15:27

Thanks you very much !!!

It's getting MLE7 . I did as you said!

Edited by author 24.01.2018 22:56

Edited by author 24.01.2018 22:56

Thank you

new compilers "eat" more memory

oh, really?
I am wondering how is it possible at all to store n/2 elements in the heap (for n=250k we use 32 bits times 125000 / 2^20 and thus we get approximately 3.815MB) and not to get MLE there.

Bits 32*125000 = 4e+6 bits
We know that 1Mb = 8e+6 bits

So we end up getting 0.5 MB if storing n/2 elements. And exactly 1MB for storing n elements.

Edited by author 14.10.2020 17:20

Edited by author 14.10.2020 17:20