Please can you explain, why i got MLE 7 #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 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 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 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 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. . 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. . 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? |