Zadanie

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 Krtkove1 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ň.

Úloha

Vašou úlohou bude simulovať čakáreň. Čakáreň pozostáva z dvoch typov akcií. Buď sa niekto s celočíselnou prioritou2 \(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.

Formát vstupu

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\).

Formát výstupu

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.

Príklad

Input:

10
1 1
1 1
0 0
1 6
0 0
1 2
0 0
0 0
1 4
0 0

Output:

1
1
1
6
1
2
1
prazdna
4
prazdna

  1. niečo ako Kocúrkovo↩︎

  2. Áno, každý v Krtkove má nejakú prioritu na očkovanie↩︎

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';
        }
    }
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.