Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment