Show all threads Hide all threads Show all messages Hide all messages | Use cstdio | pocochuk | 1306. Sequence Median | 27 Mar 2024 05:35 | 1 | | How to get AC on C++ | LeTim | 1306. Sequence Median | 13 Feb 2024 14:44 | 1 | 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 | if you have mle #7 just use visual c++ 2019 | >>> | 1306. Sequence Median | 2 Jul 2022 20:45 | 1 | g++ 9.2 - mle 7 visual c++ - AC | WA #5 | Tapti | 1306. Sequence Median | 21 Feb 2022 15:54 | 1 | WA #5 Tapti 21 Feb 2022 15:54 You should write "fixed<<setprecision(15)", because you get uncorrected format of numbers with dot | Getting MLE for this:|| | Reza Gharaghani | 1306. Sequence Median | 15 Jun 2021 13:14 | 1 | #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; } | WA #5 wrong answer | Theodike | 1306. Sequence Median | 14 Mar 2021 15:46 | 3 | 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 Try the following test: 4 2147483647 2147483647 2147483647 2147483647 | AC at last!!! | CHIDEMYAN SERGEY | 1306. Sequence Median | 14 Oct 2020 17:20 | 8 | I get AC using priority_queue<unsigned int> At first I push n/2+1 numbers then I read next number,push it to queue,pop biggest element until I have elements If n odd I use 1 top elem for answer else I use 2 top elements for answer such way: if (top1+top2) mod 2=0 I output top1/2+top2/2+top1 mod 2 and then print ".0" else I output top1/2+top2/2 and then print ".5" I hope it'll help somebody. P.S thank to authors of this problem.I like this problem very much!
Edited by author 07.02.2008 01:49 Thanks Dengin Roman 21 Mar 2012 15:24 CHIDEMYAN SERGEY, thanks a lot! You helped me very much. Finally, I passed it! Edited by author 21.03.2012 15:27 MLE husniddin351 24 Jan 2018 22:55 It's getting MLE7 . I did as you said! Edited by author 24.01.2018 22:56 Edited by author 24.01.2018 22:56 Re: MLE bstu_student 27 Aug 2018 22:20 new compilers "eat" more memory oh, really? I am wondering how is it possible at all to store n/2 elements in the heap (for n=250k we use 32 bits times 125000 / 2^20 and thus we get approximately 3.815MB) and not to get MLE there. Re: MLE lostbrain 14 Oct 2020 17:20 Bits 32*125000 = 4e+6 bits We know that 1Mb = 8e+6 bits So we end up getting 0.5 MB if storing n/2 elements. And exactly 1MB for storing n elements. Edited by author 14.10.2020 17:20 Edited by author 14.10.2020 17:20 | Memory limit exceeded for test case 7 | Foysal Ahammed | 1306. Sequence Median | 7 Aug 2020 18:43 | 3 | #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; } Priority queue uses vector under the hood. How many times vector resized while first for() executed - unknown, what final vector capacity - unknown, was all vector buffers except last freed or they still kept by allocator - unknown. I'd recommend to not use priority queue at all, I'd rather implement custom bike using fixed size buffer and std heap functions There must be no problem with vector - I used it successfully but care about its size in advance (reserve and shrink). Be careful in printing big numbers (float not enough) and in using iterators - this is the problem of memory error could be - you may point to out of vector. Also different compilers use compile program with different size and use different allocators - try to use different compilers. | WHY MLE ON TEST 7 PLEASE HELP MEEE | KiTe | 1306. Sequence Median | 26 Oct 2019 00:07 | 1 | 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 | I've tried everything but still MLE | achvanov | 1306. Sequence Median | 9 Sep 2019 22:16 | 2 | 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; } It's wrong. Because the last leaf of the max heap is not necessarily minimum but you are removing it (v.pop_back();). Your code may remove the median element. And the sort_heap has no effect. | Что значит (технически) ограничение по памяти. | Konstantin | 1306. Sequence Median | 15 Apr 2019 16:41 | 1 | Здравствуйте. Это хорошо задача (для медианы не существует хорошего агрегата) требующая для точного решения хранения минимум N\2 чисел. И тем более эффективная по времени решения, чем больше чисел мы одновременно можем хранить. Поэтому хотелось бы точно знать что значит ограничение на 1MБ по памяти. | why... this is wrong answer | Iqramul Islam | 1306. Sequence Median | 6 Jan 2019 11:18 | 1 | #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)); } | Как уменьшить расход памяти? | Fitman | 1306. Sequence Median | 12 Jun 2017 17:55 | 2 | Вот код... Я не понимаю как уменьшить расход памяти... но программа написана верно и работает... #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];} } Не храни 250 000 unsigned int 'ов. Храни, например, только половину -- 125 000. Тогда, очевидно, расход памяти сократится в два раза. Edited by author 12.06.2017 17:55 | WA #5 | Accepted | 1306. Sequence Median | 18 Feb 2017 20:26 | 4 | WA #5 Accepted 2 Mar 2013 12:05 I use priority queue,the memory that I used is 236 KB,but I still WA at test 5,but I don't know why... You need use unsigned int. could someone tell me why ? Edited by author 18.02.2017 05:40 Edited by author 18.02.2017 05:40 2^31-1 can be stored into signed int. But, when length of input is even, you need to value average, so (probably) add 2 values and receive integer overflow. It doesn't mean you must use unsigned. You can avoid overflow in any other way. | Please can you explain, why i got MLE 7 | Rocky.B | 1306. Sequence Median | 12 Jan 2017 14:37 | 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 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? | TEST#6 | sano23 | 1306. Sequence Median | 7 Nov 2016 02:21 | 1 | TEST#6 sano23 7 Nov 2016 02:21 does anyone knows test 6? | Different status with different compilers | Infoshoc | 1306. Sequence Median | 9 Sep 2016 21:48 | 1 | The same solution receives ML#7 with c++ compilers and AC with c. Pay attention to it | MLE #7? | GorinichNainaKievna | 1306. Sequence Median | 1 Aug 2016 01:17 | 7 | MLE #7? GorinichNainaKievna 31 Jul 2016 16:10 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; }
>int a[250000]; Empty helloworld already shows 100+ kb, so 250000 is not an option. The only way is to use ~200000 or so numbers. So why I don't have MLE #1? Because first 6 tests have a small N, and thus most of this array isn't initialized and used. Try to fill your array with random numbers in the beginning of your main() and you'll have MLE #1. By the way. std::nth_element(a, a + n / 2, a + n); // (1) std::nth_element(a, a + n / 2 - 1, a + n); // (2) Are you sure it must work? I suppose value found on step 1 can be moved on step 2. | Anyone have any ideas on what Test 8 is doing? | SquidBoy | 1306. Sequence Median | 2 Jul 2016 12:59 | 4 | Had some issues implementing the heap, and then realised had a nice Access Violation (didn't bother to check we weren't exceeding the bounds on the heaps underlying array). Now I'm stuck on Test #8 - but I've tried every test I've seen suggested in the comments....Anyone got a nice test to try ??? I've even tried generating up to about 190000 random numbers < 2^31-1 in Excel (3 columns) and my median always agrees with theirs.... I've Also tried the same number of ordered numbers (incrementing by 1) as well as random but sorted numbers in a single column (sorted in both directions). I suspect I have some silly output issue (rather than a logic issue - but that might just be because I;m arrogant). Ok, for those who have trouble with test 8. Apparently 0 is a valid value in the tests (I'd assumed that POSITIVE meant "strictly greater than 0" - I would have thought including 0 is NON-NEGATIVE rather than POSITIVE). Once I catered for the possibility of 0 in the heap, everything was happy.... In my case I was getting wrong one of the elements for the semi-sum. | Any ideas what test #17 is? | ToadMonster | 1306. Sequence Median | 28 Mar 2016 15:24 | 3 | Lost ac. WA 17 Looks like it isn't "n<=0", it isn't about integer overflow during even-length sequence overflow calculation. Edit: oh alright, congratulations. Edited by author 28.03.2016 16:15 Thanks, finally got AC. Was childish error in checking if N is odd or even. |
|
|