bolachas.cpp

#include<bits/stdc++.h>
using namespace std;
 
int tot; //total de inteiros sendo analisados
string s;//string auxiliar para ler a entrada
multiset<int> menores, maiores; 
 
int main(){
    while(cin >> s){ //leremos até acabar a entrada
        if(s[0] == '#'){
            if(tot % 2==0){
                printf("%d\n",*maiores.begin()); //pelo método que usamos, a mediana sempre será o menor valor dos maiores
                maiores.erase(maiores.begin());
                multiset<int>::iterator it=menores.end();
                it--;
                maiores.insert(*it);
                menores.erase(it); //rebalanceamos as estruturas, para garantir a proprieadade da mediana.
            }else{
                printf("%d\n",*maiores.begin());
                maiores.erase(maiores.begin());//não é necessario rebalancear, 
                                                //ja que agora ambas as estruturas terão a mesma quantia de números
            }
            tot--; //como retiramos um valor, podemos subtrair o total   
        }
        else{
            int i = stoi(s); //convertemos a string para um número
            if(tot%2==0){
                menores.insert(i);
                multiset<int>::iterator it=menores.end();
                it--;
                maiores.insert(*it); //inserimos o numero na estrutura menor, e rebalanceamos para garantir a propriedade
                menores.erase(it);
            }else{
                maiores.insert(i);              
                menores.insert(*maiores.begin());
                maiores.erase(maiores.begin());
                //inserimos o numero na estrutura maior, e rebalanceamos para garantir a propriedade
                //para garantir que ambas as estruturas tenham o mesmo tamanho.
            }
            tot++;
        }
    }
    return 0;
}