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

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

I've tried everything but still MLE
Послано achvanov 30 мар 2019 12:36
I've tried priority_queue and heap, but still MLE. Here's my code, can somebody help me?
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
    int n, a;
    std::cin >> n;
    std::vector<int> v(n / 2 + 1);
    for (int i = 0; i < n / 2 + 1; ++i) {
        std::cin >> v[i];
    }
    std::make_heap(v.begin(), v.end());
    for (int i = 0; i < (n + 1) / 2 - 1; ++i) {
        std::cin >> a;
        v.push_back(a);
        std::push_heap(v.begin(), v.end());
        std::pop_heap(v.begin(), v.end());
        v.pop_back();
    }
    std::sort_heap(v.begin(), v.end());
    if (n % 2) {
        std::cout << v.back() << ".0";
    }
    else {
        a = v.back();
        v.pop_back();
        std::cout << (0ll + a + v.back()) / 2 << '.';
        if ((0ll + a + v.back()) % 2) {
            std::cout << 5;
        }
        else {
            std::cout << 0;
        }
    }

    return 0;
}
It's WA.
Послано lnxdx 9 сен 2019 22:16
It's wrong. Because the last leaf of the max heap is not necessarily minimum but you are removing it (v.pop_back();). Your code may remove the median element.

And the sort_heap has no effect.