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

Please can you explain, why i got MLE 7
Posted by Rocky.B 1 Dec 2016 20:50
#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
Re: Please can you explain, why i got MLE 7
Posted by ToadMonster 1 Dec 2016 21:17
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.
Re: Please can you explain, why i got MLE 7
Posted by Rocky.B 3 Dec 2016 14:16
Please can you show, how it can be done.
I can't do it

Edited by author 03.12.2016 14:16
Re: Please can you explain, why i got MLE 7
Posted by Rocky.B 3 Dec 2016 14:18
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);
Re: Please can you explain, why i got MLE 7
Posted by ToadMonster 3 Dec 2016 15:21
Google std::make_heap / std::push_heap / std::pop_heap

Don't use priority queue at all
You may use Kth order statistics algorithm there. .
Posted by xurshid_n 12 Jan 2017 01:46
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!!!
Re: You may use Kth order statistics algorithm there. .
Posted by ToadMonster 12 Jan 2017 14:37
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