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 1306. Sequence Median

AC at last!!!
Posted by CHIDEMYAN SERGEY 7 Feb 2008 01:48
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
Thanks
Posted by Dengin Roman 21 Mar 2012 15:24
CHIDEMYAN SERGEY, thanks a lot! You helped me very much. Finally, I passed it!

Edited by author 21.03.2012 15:27
Re: Thanks
Posted by YÊU HÀ NHẤT 27 Mar 2015 21:03
Thanks you very much !!!
MLE
Posted by husniddin351 24 Jan 2018 22:55
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
Re: AC at last!!!
Posted by Mutasim Billah 9 Mar 2018 21:44
Thank you
Re: MLE
Posted by bstu_student 27 Aug 2018 22:20
new compilers "eat" more memory
Re: MLE
Posted by Gleb 17 Jan 2019 14:15
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.
Re: MLE
Posted by lostbrain 14 Oct 2020 17:20
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