ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1306. Медиана последовательности

AC at last!!!
Послано CHIDEMYAN SERGEY 7 фев 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
Послано Dengin Roman 21 мар 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
Послано YÊU HÀ NHẤT 27 мар 2015 21:03
Thanks you very much !!!
MLE
Послано husniddin351 24 янв 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!!!
Послано Mutasim Billah 9 мар 2018 21:44
Thank you
Re: MLE
Послано bstu_student 27 авг 2018 22:20
new compilers "eat" more memory
Re: MLE
Послано Gleb 17 янв 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
Послано lostbrain 14 окт 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