competitive-programming/minMaxHeap.cpp at master · rsaphala/competitive-programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <iomanip>

#define endl '\n'
using namespace std;

priority_queue<int>maxQ;
priority_queue<int, vector<int>, greater<int> > minQ;

double solve(int n){
    if (maxQ.empty()) maxQ.push(n);
    else if (minQ.empty()) minQ.push(n);
    else {
        if (maxQ.size() == minQ.size()){
            maxQ.push(n);
        } else if (maxQ.size() > minQ.size()){
            minQ.push(n);
        } else maxQ.push(n);
    }

    if (maxQ.size() == 1 && minQ.empty()) return maxQ.top();

    if (maxQ.top() > minQ.top()){
        int tempMax = maxQ.top();
        int tempMin = minQ.top();
        maxQ.pop();minQ.pop();
        maxQ.push(tempMin);minQ.push(tempMax);
    }

    int sz = maxQ.size() + minQ.size();
    if (sz % 2){
        if (maxQ.size() > minQ.size()) return maxQ.top();
        else return minQ.top();
    } else {
        double a = maxQ.top();
        double b = minQ.top();
        return (a+b)/2;
    }
}

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int a_i = 0;a_i < n;a_i++){
       cin >> a[a_i];
       cout << fixed << setprecision(1) << solve(a[a_i]) << endl;
    }
    return 0;
}