ural 1306. Sequence Median

 1 #include <cstdio>
 2 #include <queue>
 3 #include <iostream>
 4 using namespace std;
 5 inline void SetIO(string Name)
 6 {
 7     string Input = Name+".in",
 8     Output = Name+".out";
 9     freopen(Input.c_str(), "r", stdin),
10     freopen(Output.c_str(), "w", stdout);
11 }
12 
13 int n, Arr[250000 / 2 + 5];
14 
15 inline void Input() 
16 {
17     scanf("%d", &n);
18 }
19 
20 inline void Solve()
21 {
22     for(int i = 0; i < n / 2 + 1; i++) scanf("%d", &Arr[i]);
23     make_heap(Arr, Arr + n / 2 + 1);
24     for(int i = n / 2 + 1; i < n; i++)
25     {
26         scanf("%d", &Arr[n / 2 + 1]);
27         push_heap(Arr, Arr + n / 2 + 2);
28         pop_heap(Arr, Arr + n / 2 + 2);
29     }
30     if(n & 1) printf("%.1lf\n",1.0 * Arr[0]);
31     else
32     {
33         unsigned int x = Arr[0];
34         pop_heap(Arr, Arr + n / 2 + 1);
35         unsigned int y = Arr[0];
36         printf("%.1lf\n", 1.0 * (x + y) / 2.0);
37     }
38 }
39 
40 int main()
41 {
42     #ifndef ONLINE_JUDGE 
43     SetIO("G");
44     #endif 
45     Input();
46     Solve();
47     return 0;
48 }