Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Miškovi na [email protected]
Táto úloha je o dátovej štruktúre - Halda. Ak nevieš čo Halda je, môžeš si o nej viac prečítať v študíjnom texte o Halde.
V Krtkove^[niečo ako Kocúrkovo] majú teraz nový problém. Je viac ľudí, ktorí sa chcú dať zaočkovať ako vakcín. Rozhodli sa preto, že spravia čakáreň, do ktorej sa môžu ľudia zapísať a počkať, kým pre nich bude k dispozícii vakcína. Ostáva už len jeden problém a to koho zavolať na očkovanie ako prvého. Keďže všetci v Krtkove sú zaneprázdnení, potrebujú niekoho kto im naprogramuje čakáreň.
Vašou úlohou bude simulovať čakáreň. Čakáreň pozostáva z dvoch typov akcií. Buď sa niekto s celočíselnou prioritou^[Áno, každý v Krtkove má nejakú prioritu na očkovanie] $p$ prihlási do čakárne alebo máme novú vakcínu, teda človek s najväčšou prioritou bude zaočkovaný a odíde z čakárne. Po každej akcii nás zaujíma, aká je najväčšia priorita medzi ľuďmi v čakárni. Na začiatku je čakáreň prázdna.
Na prvom riadku sa nachádza číslo $n$ - počet akcií ktoré treba spracovať. Nasleduje $n$ riadkov, $i$-ty z nich popisuje $i$-tu akciu a má tvar $t\ x$. Ak $t$ je $0$, tak prišla nová vakcína a $x$ ignorujeme. Ak $t$ je $1$, tak sa do čakárne prihlásil nový človek s prioritou $x$. V prvej akcii sme ponechali na vstupe $x$ kvôli ľahšiemu načítavaniu vstupu (pre obe akcie treba načítať dve čísla).
Je zaručené, že ak prišla nová vakcína v čakárni je aspoň jeden človek. Vo všetkých sadách platí, že $1 \leq n \leq 2 \cdot 10^5$ a $1 \leq x \leq 10^9$.
Vypíšte $n$ riadkov, v $i$-tom jedno celé číslo - najväčšia priorita spomedzi ľudí v čakárni po $i$ akciách. Ak je po $i$-tej akcii čakáreň prázdna, vypíšte namiesto toho prazdna.
10
1 1
1 1
0 0
1 6
0 0
1 2
0 0
0 0
1 4
0 0
1
1
1
6
1
2
1
prazdna
4
prazdna
V tejto úlohe nám stačí spraviť obyčajnú maximovú haldu, ktorá bude zvládať dve operácie - push a pop. To ako, prečo, ako rýchlo… halda funguje bolo v študíjnom texte o Halde. Teraz si ukážeme už len implementáciu.
Python:
pole = []
def push(co):
pole.append(co)
kde = len(pole) - 1
while kde > 0:
rodic = (kde - 1) // 2
if pole[kde] > pole[rodic]:
pole[kde], pole[rodic] = pole[rodic], pole[kde]
kde = rodic
else:
break
def pop():
n = len(pole)
pole[0], pole[n-1] = pole[n-1], pole[0]
pole.pop()
kde = 0
while True:
kam = kde
if 2*kde+1 < n-1 and pole[2*kde+1] > pole[kam]:
kam = 2*kde+1
if 2*kde+2 < n-1 and pole[2*kde+2] > pole[kam]:
kam = 2*kde+2
if kam != kde:
pole[kde], pole[kam] = pole[kam], pole[kde]
kde = kam
else:
break
n = int(input())
for i in range(n):
t, x = map(int, input().split())
if t == 0:
pop()
if len(pole) == 0:
print('prazdna')
else:
print(pole[0])
if t == 1:
push(x)
print(pole[0])
C++:
#include <iostream>
#include <vector>
using namespace std;
void push(int co, vector<int> &p)
{
p.push_back(co);
int kde = p.size() - 1;
while (kde > 0)
{
int rodic = (kde-1)/2;
if (p[kde] > p[rodic])
{
swap( p[kde], p[rodic] );
kde = rodic;
} else break;
}
}
void pop(vector<int> &p)
{
int n = p.size();
swap( p[0], p[n-1] );
p.pop_back();
int kde = 0;
while (true)
{
int kam = kde;
if (2*kde+1 < n-1 && p[2*kde+1] > p[kam]) kam = 2*kde+1;
if (2*kde+2 < n-1 && p[2*kde+2] > p[kam]) kam = 2*kde+2;
if (kam != kde)
{
swap( p[kde], p[kam] );
kde = kam;
}
else break;
}
}
int main()
{
vector<int> pole;
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
int t, x;
cin >> t >> x;
if(t == 0)
{
pop(pole);
if(pole.size() == 0)
{
cout << "prazdna\n";
}
else
{
cout << pole[0] << '\n';
}
}
if(t == 1)
{
push(x, pole);
cout << pole[0] << '\n';
}
}
}