#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <queue>

#define f first
#define s second

#define ll long long
#define ld long double
#define ull unsigned long long

#define pb push_back
#define ppb pop_back
#define mp make_pair

#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define bit(x) __builtin_popcountll(x)
#define sqr(x) ((x) * 1LL * (x))

#define nl '\n'
#define ioi exit(0);

#define NeedForSpeed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define _7day "IOI2017"

using namespace std;

typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ld, ld> pdd;
typedef pair <ll, ull> hack;

const int N = 1e5 + 7, MxN = 1e6 + 7, mod = 1e9 + 7, inf = 1e9 + 7;
const long long linf = (ll)1e18 + 7;
const long double eps = 1e-15, pi = 3.141592;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};


    int n, x;
    priority_queue <unsigned int> q;
int main(){
    #ifndef _7day
        freopen (_7day".in", "r", stdin);
        freopen (_7day".out", "w", stdout);
    #endif

    cin >> n;
    for (int i = 1; i <= n / 2 + 1; ++i)
        cin >> x, q.push(x);
    for (int i = n / 2 + 2; i <= n; ++i){
        cin >> x;
        if (x < q.top()) q.pop(), q.push(x);
    }

    if (n % 2) printf ("%d.0", q.top());
    else{
        unsigned int top1 = q.top();
        q.pop();
        if ((top1 + q.top()) % 2 == 0) cout << top1 / 2 + q.top() / 2 << ".0";
        else cout << top1 / 2 + q.top() / 2 << ".5";
    }
    ioi
}

Edited by author 01.12.2016 20:51

Edited by author 01.12.2016 20:51

Priority queue is based on vector. When vector resizes, 2 data blocks can be allocated in one time.

Let it resizes at n/2 size/capacity. Next data block capacity (assuming resize factor 1.5) is 3n/4. Even second block can cause MLE. Both blocks size is 5*n/4 - MLE.

You should avoid resizing. You should better set fixed vector size (approx n/2+2) and use heap functions over it.

Please can you show, how it can be done.
I can't do it

Edited by author 03.12.2016 14:16

I tried to do like this but whatever it's got MLE 7
vector <unsigned int> vec;
vec.reserve(n / 2 + 2);
priority_queue <unsigned int> q (less<unsigned int>(), vec);

Google std::make_heap / std::push_heap / std::pop_heap

Don't use priority queue at all

std::nth_element. but need a little tricky

  for n <= 2*10^5  --> read all numbers and use direct nth_element (or your own implementation of Kth order statistics).
   for  n > 2*10^5  --> read only 2*10^5 numbers and use nth_element for n - 2*10^5, and remove first n - 2*10^5, i.e. rewrite remain numbers to first n-2*10^5, and again use nth_element for n/2 - (n- 2*10^5)

Good Luck!!!

I see you got AC, but this description looks suspicious anyway.

Let we need to process 9 elements [1,2,3,4,5,6,7,8,9] in any order (so expected answer is 5), and have 5 elements array.

As I understand steps should be:
for  n > 5  --> (1)read only 5 numbers and use nth_element for n - 5,
(2) remove first n - 5, i.e. rewrite remain numbers to 5,
(3) again use nth_element for n/2 - (n- 5)
Am I correct?

Let see numbers in order [1,2,5,8,9,3,4,6,7]
Read first 5, find (9-5) = 4th:
[1,2,5,8,9] => 9 (or 8), rest removed. 5 removed, wont be answer, fail

Could you please show your code?