Обсуждение @ 1306. Медиана последовательности @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

use priority_queue <unsigned int>!!!! Dan.hu 3 фев 2007 13:07

Re: use priority_queue <unsigned int>!!!! Fyodor Menshikov 3 фев 2007 14:49

With 1 Mb memory limit? :-)

Re: use priority_queue <unsigned int>!!!! Roma Labish[Lviv NU] 10 фев 2007 19:24

AC now:)

Edited by author 11.02.2007 15:03

Re: use priority_queue <unsigned int>!!!! KIRILL(ArcSTU) 10 фев 2007 20:55

You should store in queue n/2 +1 numbers

Re: use priority_queue <unsigned int>!!!! Roma Labish[Lviv NU] 10 фев 2007 22:53

I can't understand you... How I can do it?

Re: use priority_queue <unsigned int>!!!! KIRILL(ArcSTU) 10 фев 2007 23:40

At first push n/2+1 numbers then do this
1 read next number
2 push it to queue
3 pop biggest element
4 goto 1
At the end use 2 or 1 top elements for answer

Re: use priority_queue <unsigned int>!!!! Roma Labish[Lviv NU] 11 фев 2007 00:00

Thank you very much!!! I got AC!

Re: use priority_queue <unsigned int>!!!! CHIDEMYAN SERGEY 22 авг 2007 03:21

I use priority queue as you said,but still MLE#7.Maybe I'm wrong,here is my code:
#include<iostream>
using namespace std;
#include<queue>
int main()
{std::priority_queue<int>pr;
int n,i,a;
    cin>>n;
for(i=1;i<=n/2+1;i++)
    {cin>>a;
    pr.push(a);
    }
i=n/2+2;
    while(i<=n){
        cin>>a;
        pr.push(a);i++;
pr.pop();
}
if(n%2!=0)
cout<<pr.top()<<".0"<<endl;
else
{a=pr.top();
pr.pop();
if(a%2+pr.top()%2==2)
cout<<a/2+pr.top()/2+1<<".0"<<endl;
    else
        if(a%2+pr.top()%2==0)
        cout<<a/2+pr.top()/2<<".0"<<endl;
        else
            if(a%2+pr.top()%2==1)
            cout<<(a/2+pr.top()/2)<<".5"<<endl;
}
return 0;
}
Thank!!!

Edited by author 18.09.2007 19:59

try *_heap (+) ASK 28 фев 2010 18:29

   int v[250000/2+3];
   for(; i < n/2+1; ++i) cin >> v[i];
   make_heap(v,v+n/2+1);
   for(; i < n; ++i){
     cin >> v[n/2+1];
     push_heap(v,v+n/2+2);
     pop_heap(v,v+n/2+2);
   }

BTW(1), there is no need for "unsigned" since input is less than 2^31-1

BTW(2), there is no need to avoid "double a" in calculation and output of the the final answer:

cout << setprecision(1) << fixed << a << endl;

Re: try *_heap (+) Name must be given in English 14 май 2010 13:23

ASK писал(a) 28 февраля 2010 18:29

BTW(1), there is no need for "unsigned" since input is less than 2^31-1

There was an example of possible input in early posts on the forum:

[(2^31 - 1) + (2^31 - 1)] / 2 = 2^31 - 1

but

((2^31) - 1) + ((2^31) - 1) = 4 294 967 294

so if you don't know how to manage such a thing you should use unsigned int.
BTW there is no differences in allocated memory between "unsigned" and "signed int" but "unsigned" work faster.

Re: try *_heap (+) panhantao 29 ноя 2011 07:38

one way to avoid overflow of calculating ((2^31) - 1) + ((2^31) - 1) is to compute
((2^31-1) * 0.5) + ((2^31-1) * 0.5) instead of ( ((2^31) - 1) + ((2^31) - 1) ) * 0.5

Re: use priority_queue <unsigned int>!!!! hello_world_ww 24 ноя 2012 10:00

thank you very much!

Re: use priority_queue <unsigned int>!!!! Pegasus 23 мар 2013 14:22

I have learnt a lot ,thanks.

Re: use priority_queue <unsigned int>!!!! andy_21 4 окт 2015 17:40

I use G++ 4.9 and get MLE. Then I try G++ 4.9 C++ 11 and AC.
Why? :(

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