With 1 Mb memory limit? :-)

AC now:)

Edited by author 11.02.2007 15:03

You should store in queue n/2 +1 numbers

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

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

Thank you very much!!! I got AC!

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

   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;

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.

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

thank you very much!

I have learnt a lot ,thanks.

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