|
|
вернуться в форумMLE on test#7 Послано Denis 6 фев 2008 14:57 I use heap sort without any recursion. I have no idea where I can have MLE. Please, help me. Here is my code: #include <fstream> #include <stdio.h> using namespace std; int n, nm = 0; unsigned int arr[250010] = {0}; void hinsert (unsigned int k) { unsigned int i; arr[++nm] = k; i = nm; while (i > 1 && arr[i/2] < arr[i]) { swap (arr[i], arr[i/2]); i /= 2; } } unsigned int ex_max () { unsigned int Res = arr[1]; arr[1] = arr[nm--]; //mh (1); unsigned int i = 1; unsigned int l, r, res = i; while (1) { l = 2*i; r = 2*i+1; if (l <= nm && arr[l] > arr[res]) { res = l; } if (r <= nm && arr[r] > arr[res]) { res = r; } if (res != i) { swap (arr[i], arr[res]); i = res; } else { break; } } return Res; } int main () { //freopen ("a.in", "r", stdin); //freopen ("a.out", "w", stdout); unsigned int i, j, t; scanf ("%d", &n); t = n; int s = t*3/4; t -= s; double vl; while (s--) { scanf ("%lf", &vl); j = (unsigned int)(vl); hinsert (j); } while (t--) { scanf ("%lf", &vl); j = (unsigned int)(vl); hinsert (j); } while (nm > 0) { j = ex_max (); arr[nm+1] = j; } long long int ans; if (n%2 == 1) { ans = (long long int)(arr[(n+1)/2]); printf ("%I64d\n", ans); } else { ans = (long long int)(arr[n/2])+(long long int)(arr[n/2+1]); if (ans%2 == 1) { ans /= 2; printf ("%I64d.5\n", ans); } else { ans /= 2; printf ("%I64d\n", ans); } } return 0; } |
|
|