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

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

MLE on test#7
Послано Denis 6 фев 2008 14:57
I use heap sort without any recursion. I have no idea where I can have MLE.
Please, help me.
Here is my code:
#include <fstream>
#include <stdio.h>
using namespace std;

int n, nm = 0;
unsigned int arr[250010] = {0};

void hinsert (unsigned int k)
{
    unsigned int i;
    arr[++nm] = k;
    i = nm;
    while (i > 1 && arr[i/2] < arr[i])
    {
        swap (arr[i], arr[i/2]);
        i /= 2;
    }
}

unsigned int ex_max ()
{
    unsigned int Res = arr[1];
    arr[1] = arr[nm--];
    //mh (1);
    unsigned int i = 1;
    unsigned int l, r, res = i;
    while (1)
    {
        l = 2*i;
        r = 2*i+1;
        if (l <= nm && arr[l] > arr[res])
        {
            res = l;
        }
        if (r <= nm && arr[r] > arr[res])
        {
            res = r;
        }
        if (res != i)
        {
            swap (arr[i], arr[res]);
            i = res;
        }
        else
        {
            break;
        }
    }
    return Res;
}

int main ()
{
    //freopen ("a.in", "r", stdin);
    //freopen ("a.out", "w", stdout);
    unsigned int i, j, t;
    scanf ("%d", &n);
    t = n;
    int s = t*3/4;
    t -= s;
    double vl;
    while (s--)
    {
        scanf ("%lf", &vl);
        j = (unsigned int)(vl);
        hinsert (j);
    }
    while (t--)
    {
        scanf ("%lf", &vl);
        j = (unsigned int)(vl);
        hinsert (j);
    }
    while (nm > 0)
    {
        j = ex_max ();
        arr[nm+1] = j;
    }
    long long int ans;
    if (n%2 == 1)
    {
        ans = (long long int)(arr[(n+1)/2]);
        printf ("%I64d\n", ans);
    }
    else
    {
        ans = (long long int)(arr[n/2])+(long long int)(arr[n/2+1]);
        if (ans%2 == 1)
        {
            ans /= 2;
            printf ("%I64d.5\n", ans);
        }
        else
        {
            ans /= 2;
            printf ("%I64d\n", ans);
        }
    }
    return 0;
}