Yes, weird.

1. Use scanf/printf instead of cin/cout
2. Use make_heap, push_heap and pop_heap instead of priority_queue
3. Use C-style array instead of vector
4. Do not allocate n elements for an array

g++ 9.2 - mle 7
visual c++ - AC

You should write "fixed<<setprecision(15)", because you get uncorrected format of numbers with dot

#include<algorithm>
#include<cstdio>
using namespace std;
#define MAX_N 250000

int n, i, t1, t2;
int *heap;

int main(){
    scanf("%d", &n);
    heap = new int[n/2+2];
    for(i = 0; i < n/2+1; ++i){
        scanf("%d", heap+i);
        push_heap(heap, heap+i+1);
    }

    for(i = 0; i < n/2-(n+1)%2; ++i){
        scanf("%d", heap+n/2+1);
        push_heap(heap, heap+n/2+2);
        pop_heap(heap, heap+n/2+2);
    }

    if(n%2){
        printf("%d.0\n", heap[0]);
    }else{
        t1 = heap[0];
        pop_heap(heap, heap+n/2+1);
        t2 = heap[0];
        if((t1+t2)%2){
            printf("%d.5\n", t1/2+t2/2);
        }else{
            printf("%d.0\n", t1/2+t2/2+t1%2);
        }
    }
    delete[] heap;

    return 0;
}

#include <bits/stdc++.h>
#include<cstdio>
#include <queue>
#define pb push_back
#define mp make_pair
//Macro
#define eps 1e-9
#define pi acos(-1.0)
#define ff first
#define ss second
#define re return
#define QI queue
#define SI stack
#define SZ(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define sq(a) ((a)*(a))
#define distance(a,b) (sq(a.x-b.x) + sq(a.y-b.y))
#define iseq(a,b) (fabs(a-b)<eps)
#define eq(a,b) iseq(a,b)
#define ms(a,b) memset((a),(b),sizeof(a))
#define G() getchar()
#define MAX3(a,b,c) max(a,max(b,c))
#define II ( { int a ; read(a) ; a; } )
#define LL ( { Long a ; read(a) ; a; } )
#define DD ({double a; scanf("%lf", &a); a;})

double const EPS=3e-8;
using namespace std;

#define FI freopen ("input_B.txt", "r", stdin)
#define FO freopen ("output_B.txt", "w", stdout)

typedef long long Long;
typedef long long int64;


//For loop

#define forab(i, a, b) for (__typeof (b) i = (a) ; i <= b ; ++i)
#define rep(i, n) forab (i, 0, (n) - 1)
#define For(i, n) forab (i, 1, n)
#define rofba(i, a, b) for (__typeof (b)i = (b) ; i >= a ; --i)
#define per(i, n) rofba (i, 0, (n) - 1)
#define rof(i, n) rofba (i, 1, n)
#define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
#define for1(i, a, b) for(int i=a; i<b; i++)

template< class T > T gcd(T a, T b) { return (b != 0 ? gcd(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd(a, b) * b); }
#define __(args...) {dbg,args; cerr<<endl;}

#define __1D(a,n) rep(i,n) { if(i) printf(" ") ; cout << a[i] ; }
#define __2D(a,r,c,f) forab(i,f,r-!f){forab(j,f,c-!f){if(j!=f)printf(" ");cout<<a[i][j];}cout<<endl;}

signed main ()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);cin.tie(0);

    int n;
    unsigned int a;
    priority_queue <unsigned int> pq;

    scanf("%d", &n);

    bool odd = (n%2==1);

    for(int i=n/2; i>=0; --i){
        scanf("%u", &a);
        pq.push(a);
    }
    n-=n/2+1;

    for(int i=0; i<n; i++){
        scanf("%u", &a);
        pq.push(a);
        pq.pop();
    }
    if(odd)printf("%u\n", pq.top());
    else{
        a=pq.top();
        pq.pop();

       // cout << fixed << setprecision(1) << (a+pq.top())/2.0 << endl;
       printf("%.1f\n", (a + pq.top() ) / 2.0);
    }
    return 0;
}

MY CODE IS:

#include<bits/stdc++.h>
using namespace std;

vector < int > heap;

/////MINHEAP

void ADD( int m )
{
  heap.push_back(m);
  int j = heap.size()-1;

  while( j != 1 &&  heap[j] < heap[j/2] )
  {
    //SWAP
    int carry = heap[j/2];
    heap[j/2] = heap[j];
    heap[j] = carry;

      j /= 2;
  }
  return;
}

void REMOVEMIN()
{
  heap[1] = heap[heap.size()-1];
  heap.pop_back();

  int j = 1;

  while( ( 2*j < heap.size() &&  heap[j] > heap[2*j] ) || ( 2*j+1 < heap.size() && heap[j] > heap[2*j+1] ) )
  {
      if( 2*j+1 < heap.size() && heap[2*j] > heap[2*j+1] )
      {
       //SWAP
       int carry = heap[j];
       heap[j] = heap[2*j+1];
       heap[2*j+1] = carry;
       j = 2*j+1;
      }
      else
      {
       //SWAP
       int carry = heap[j];
       heap[j] = heap[2*j];
       heap[2*j] = carry;
       j = 2*j;
      }
  }
  return;
}

int GETMIN()
{
  return heap[1];
}

int n, a;

int main()
{
  ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);

  heap.push_back(-1);

  cin >> n;
 if( n % 2 == 0 )
 {
     int m = n/2 + 1;
      while(n--)
      {
         cin >> a;
         ADD(a);

        if( heap.size() - 1 > m )
        {
          REMOVEMIN();
        }
      }
  int mid1 = GETMIN();
  REMOVEMIN();
  int mid2 = GETMIN();
  bool f = 0;

  if( mid1 % 2 == 0 && mid2 % 2 == 0 )
    cout << mid1/2 + mid2/2;
  else if( ( mid1 % 2 == 1 && mid2 % 2 == 0 ) || ( mid1 % 2 == 0  && mid2 % 2 == 1 ) )
    cout << mid1/2 + mid2/2 << ".5";
  else
    cout << mid1/2 + mid2/2 + 1;
 }
 else
 {
     int m = n/2 + 1;
      while(n--)
      {
         cin >> a;
         ADD(a);
         if( heap.size() - 1 > m )
        {
          REMOVEMIN();
        }
      }
     cout << GETMIN();
 }


  return 0;
}
BUT WHY MLE? ?:'(

Edited by author 26.10.2019 00:08

Edited by author 26.10.2019 00:09

Edited by author 26.10.2019 00:09

Edited by author 26.10.2019 00:09

Здравствуйте.
Это хорошо задача (для медианы не существует хорошего агрегата) требующая для точного решения хранения минимум N\2 чисел.

И тем более эффективная по времени решения, чем больше чисел мы одновременно можем хранить.

Поэтому хотелось бы точно знать что значит ограничение на 1MБ по памяти.

I've tried priority_queue and heap, but still MLE. Here's my code, can somebody help me?
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
    int n, a;
    std::cin >> n;
    std::vector<int> v(n / 2 + 1);
    for (int i = 0; i < n / 2 + 1; ++i) {
        std::cin >> v[i];
    }
    std::make_heap(v.begin(), v.end());
    for (int i = 0; i < (n + 1) / 2 - 1; ++i) {
        std::cin >> a;
        v.push_back(a);
        std::push_heap(v.begin(), v.end());
        std::pop_heap(v.begin(), v.end());
        v.pop_back();
    }
    std::sort_heap(v.begin(), v.end());
    if (n % 2) {
        std::cout << v.back() << ".0";
    }
    else {
        a = v.back();
        v.pop_back();
        std::cout << (0ll + a + v.back()) / 2 << '.';
        if ((0ll + a + v.back()) % 2) {
            std::cout << 5;
        }
        else {
            std::cout << 0;
        }
    }

    return 0;
}

My code is here:
--------------
#include <iostream>
using namespace std;

int compare(const void * x1, const void * x2) {
    return (*(int*)x1 - *(int*)x2);
}

int main() {
    long N;
    cin >> N;
    int *m = new int [N];

    for (int i = 0; i < N; ++i) {
        cin >> m[i];
    }
    qsort(m, N, sizeof(int), compare);

    if (N % 2 == 0) {
        cout << (((m[(N - 1)/ 2] + m[N / 2]) / 2.0)*10)/10;
    }
    else {
        cout << m[N/2];
    }

    return 0;
}
--------------
Tell me please where I made a mistake

#include <iostream>
using namespace std;

/// A BST...
struct Node
{
    double data;
    struct Node *left, *right;
};
///function to create new Node in BST
struct Node *newNode(double item)
{
    struct Node *temp = new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
///function to insert a new Node
/// with given key in BST
struct Node* insert(struct Node *node, double key)
{
    ///if tree is empty, return a new node
    if(node==NULL)
        return newNode(key);
    ///otherwise, recur down the tree..
    if(key <node->data)
        node->left = insert(node->left, key);
    else if (key >node->data)
        node->right = insert(node->right, key);

    return node;
};

double counNodes(struct Node *root)
{
    struct Node *current, *pre;

    double count = 0;
    if(root==NULL)
        return count;

    current=root;
    while(current!=NULL)
    {
        if(current->left==NULL)
        {
            count++;
            current=current->right;
        }
        else
        {
            pre = current->left;
            while(pre->right !=NULL &&
                  pre->right !=current)
                    pre = pre->right;
            if(pre->right==NULL)
            {
                pre->right=current;
                current = current->left;
            }
            else
            {
                pre->right = NULL;

                count++;
                current = current->right;
            }
        }
    }

    return count;
}

///Function to find median in o(n) time and O(1) space...
double findMedian(struct Node *root)
{
    if(root == NULL)
        return 0;

    int count = counNodes(root);
    int currCount = 0;
    struct Node *current = root, *pre, *prev;

    while (current!= NULL)
    {
        if(current->left == NULL)
        {
            currCount++;
            ///odd case..
            if(count %2 !=0 && currCount == (count+1)/2)
                return prev->data;
            ///Even case...
            else if(count%2==0 && currCount == (count/2)+1)
                return (prev->data + current->data)/2;

           ///Update prev..for even no. of nodes...
           prev = current;

           current = current->right;
        }
        else
        {
            ///Find inorder predecessor of current...
            pre = current->left;
            while(pre->right!= NULL && pre->right!=current)
                pre = pre->right;
            /// make current as right child of in. pre.dec.
            if(pre->right == NULL)
            {
                pre->right = current;
                current = current->left;
            }
            /// revert the changes.. made in if part
            /// to restore the original tree.. , fix the right chid of predecessor...

            else
            {
                pre->right = NULL;
                prev = pre;

                currCount++;

                if(count%2!=0 && currCount == (count+1)/2)
                    return current->data;
                else if (count%2!=0 && currCount == (count/2)+1)
                    return (prev->data+current->data)/2;
                ///Update...for even case...

                prev = current;
                current = current->right;
            }
        }
    }
}

int main()
{
    struct Node *root = NULL;
    int n;
    double x;
    cin >> n;
    cin >> x;
    root = insert(root, x);
    for(int i=1; i<n; i++)
    {
        cin >> x;
            insert(root, x);
    }
    //cout << findMedian(root);
    //if(n%2==0)
        printf("%.1f", findMedian(root));

}

Вот код... Я не понимаю как уменьшить расход памяти... но программа написана верно и работает...

#include<iostream>
using namespace std;
int main(){
 int n,i,j;

 float x;
 cin >> n;
 unsigned int a[250000];
 for(i=1;i<=n;i++){
                  cin>>a[i];
                  }
 bool k=true;
 for (i=1;(i<n && k==true);i++){
     k=false;
     for(j=1;j<=n-i;j++){
     if (a[j]>a[j+1]) { swap(a[j],a[j+1]);
     k=true;
     }
     }
     }
     if (n%2==0){
    cout << (a[n/2]+a[n/2+1])/2;
     }
     else {cout << a[n/2];}
}

#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

does anyone knows test 6?

The same solution receives ML#7 with c++ compilers and AC with c.
Pay attention to it

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;
}

Lost ac. WA 17

Looks like it isn't "n<=0", it isn't about integer overflow during even-length sequence overflow calculation.

New tests were added. About 160 solutions got WA verdict on them.

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <stdio.h>
using namespace std;
unsigned int a[150002],k,kk,n,q,i;
int main()
{
            cin >> n;
            if(n > 150000){
                        k = n - 150000;
                        n = 150000;
            }
            for(i = 1;i < n+1; i ++){
                        cin >> a[i];
            }
            sort(a,a+n+1);
            for(i = 1; i <= k; i ++){
                        cin >> q;
                        if(a[n] > q) a[i] = q;
            }
            if(k > 0)
                        sort(a,a+n+1);
            if((n + k) % 2 == 1){
                        cout << a[ n / 2 + 1 - k]<< endl;
            }else {
                        kk = a[n / 2 - k] % 2 + a[n / 2 + 1 - k] % 2;
                        cout << (1ll * a[n / 2 - k] + a[n / 2 + 1 - k]) / 2;
                        if(kk == 1)cout << ".5";
            }
}

Update:
Please ignore - found a small bug in my implementation of heap.
******
My code works fine on
3
4294967295
4294967295
4294967295

and

4
4294967295
4294967295
4294967295
4294967295

what can that be?

If I use stl:priority_queue instead of my own heap based pq without making any other changes in the code, I get MLE on #7, i.e. #6 passes.

Edited by author 21.09.2015 01:41

Edited by author 21.09.2015 01:41