ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1306. Sequence Median

use priority_queue <unsigned int>!!!!
Posted by Dan.hu 3 Feb 2007 13:07
Re: use priority_queue <unsigned int>!!!!
Posted by Fyodor Menshikov 3 Feb 2007 14:49
With 1 Mb memory limit? :-)
Re: use priority_queue <unsigned int>!!!!
Posted by Roma Labish[Lviv NU] 10 Feb 2007 19:24
AC now:)

Edited by author 11.02.2007 15:03
Re: use priority_queue <unsigned int>!!!!
Posted by KIRILL(ArcSTU) 10 Feb 2007 20:55
You should store in queue n/2 +1 numbers
Re: use priority_queue <unsigned int>!!!!
Posted by Roma Labish[Lviv NU] 10 Feb 2007 22:53
I can't understand you... How I can do it?
Re: use priority_queue <unsigned int>!!!!
Posted by KIRILL(ArcSTU) 10 Feb 2007 23:40
At first push n/2+1 numbers then do this
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>!!!!
Posted by Roma Labish[Lviv NU] 11 Feb 2007 00:00
Thank you very much!!! I got AC!
Re: use priority_queue <unsigned int>!!!!
Posted by CHIDEMYAN SERGEY 22 Aug 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 (+)
Posted by ASK 28 Feb 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 (+)
Posted by Name must be given in English 14 May 2010 13:23
ASK wrote 28 February 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 (+)
Posted by panhantao 29 Nov 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>!!!!
Posted by hello_world_ww 24 Nov 2012 10:00
thank you very much!
Re: use priority_queue <unsigned int>!!!!
Posted by Pegasus 23 Mar 2013 14:22
I have learnt a lot ,thanks.
Re: use priority_queue <unsigned int>!!!!
Posted by andy_21 4 Oct 2015 17:40
I use G++ 4.9 and get MLE. Then I try G++ 4.9 C++ 11 and AC.
Why? :(