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

MLE #7?
Posted by GorinichNainaKievna 31 Jul 2016 16:10
Hi
I got MLE #7. Why?


#include <cstdio>
#include <algorithm>

int a[250000];

int main()
{
    int n;
    std::scanf("%d", &n);

    for (int i = 0; i < n; i++)
        std::scanf("%d", a + i);

    if (n % 2)
    {
        std::nth_element(a, a + n / 2, a + n);
        std::printf("%d\n", a[n / 2]);
    }
    else
    {
        std::nth_element(a, a + n / 2, a + n);
        std::nth_element(a, a + n / 2 - 1, a + n);
        std::printf("%.1f\n", (a[n / 2] + .0 + a[n / 2 - 1]) / 2);
    }

    return 0;
}
Re: MLE #7?
Posted by Oleg Baskakov 31 Jul 2016 16:39
>int a[250000];
Empty helloworld already shows 100+ kb, so 250000 is not an option. The only way is to use ~200000 or so numbers.
Re: MLE #7?
Posted by GorinichNainaKievna 31 Jul 2016 17:21
So why I don't have MLE #1?
Re: MLE #7?
Posted by Oleg Baskakov 31 Jul 2016 17:29
Because first 6 tests have a small N, and thus most of this array isn't initialized and used. Try to fill your array with random numbers in the beginning of your main() and you'll have MLE #1.
Re: MLE #7?
Posted by GorinichNainaKievna 31 Jul 2016 17:32
Thank you!
Re: MLE #7?
Posted by Oleg Baskakov 31 Jul 2016 17:37
You're welcome.
You can also look into other threads of this task, for example here
http://acm.timus.ru/forum/thread.aspx?id=31953&upd=635717437459918491
This code uses 200000 numbers, which i was talking about.
(and is still not removed, apparently)
Re: MLE #7?
Posted by ToadMonster 1 Aug 2016 01:17
By the way.

        std::nth_element(a, a + n / 2, a + n); // (1)
        std::nth_element(a, a + n / 2 - 1, a + n); // (2)

Are you sure it must work? I suppose value found on step 1 can be moved on step 2.