2012 - TSM

Enunț

TH, Seba, Șcuțu și Năstuț se joacă noul joc numit TSM. TSM are un sistem de tip multiplayer foarte interesant: se formează două echipe care se vor confrunta, una ce conține 4 jucători ce vor avea rol de apărători și alta ce conține un singur jucător cu rol de atacator (foarte necinstit). Mygo a auzit că cei 4 prieteni și-au făcut echipă, iar pe el nu l-au invitat, așa că decide să îi provoace la joc. Într-o rundă de joc acțiunile se petrec pe un câmp de luptă, inițial gol, iar apărătorii disting următoarele evenimente:

1 x : TH observă că Mygo a trimis pe câmpul de luptă un tanc de coeficient x și își anunță aliații.

2 K : Seba consideră că cel mai periculos tip de tanc aflat pe câmpul de luptă este cel cu al K – lea cel mai mic coeficient și îl afișează în consolă, pe un nou rând.

3 : Năstuț scrie în consolă, pe un nou rând, coeficientul cel mai mic al unui tanc aflat în momentul respectiv pe câmpul de luptă.

4 : Șcuțu trage cu tunul într-un tanc de coeficient egal cu ultimul scris de Seba în consolă și îl elimină.

Cerința

Pentru un joc cu M evenimente, simulați parcursul jocului.

Cei 4 prieteni au folosit aceste două bucăți de cod ca să poată să câștige, așa că ți le oferă și ție:

InParser

OutParser

Date de intrare

Fișierul de intrare tsm.in conține pe prima linie numărul M, reprezentând numărul de evenimente, iar pe următoarele M linii câte un eveniment, cu formatul explicat mai sus.

Date de ieșire

Fișierul de ieșire tsm.out va conține pentru fiecare eveniment de tipul 2 și 3, răspunsul lor, fiecare pe câte o linie, în ordinea în care acestea apar în fișierul de intrare.

Restricții și precizări

• 1 ≤ M ≤ 1.000.000
• pentru evenimentele de tip 1, 1 ≤ x ≤ 1.000.000
• se garantează că orice alt eveniment va putea fi procesat.
• între oricare 2 evenimente de tip 4 va exista cel puțin un eveniment de tip 2.

Exemplu:

tsm.in

14
1 2
1 3
3
1 2
1 1
1 1
3
1 4
2 3
2 1
4
2 1
4
3

tsm.out

2
1
3
1
1
2

Rezolvare

from heapq import heappush, heappop

def main():
    events = []  # Lista de evenimente
    tanks = []  # Coada de tancuri (heap)

    with open("tsm.in", "r") as fin, open("tsm.out", "w") as fout:
        m = int(fin.readline())  # Numărul de evenimente

        for _ in range(m):
            event = fin.readline().split()
            event_type = int(event[0])
            events.append(event)

        for event in events:
            event_type = int(event[0])

            if event_type == 1:
                tank_coeff = int(event[1])
                heappush(tanks, tank_coeff)

            elif event_type == 2:
                k = len(tanks)
                if k > 0:
                    temp_tanks = tanks.copy()
                    temp_tanks.sort()
                    fout.write(str(temp_tanks[k - int(event[1])]) + "\n")

            elif event_type == 3:
                if tanks:
                    fout.write(str(tanks[0]) + "\n")

            elif event_type == 4:
                if tanks:
                    tank_to_remove = heappop(tanks)
                    while tanks and tank_to_remove != tanks[0]:
                        tank_to_remove = heappop(tanks)

if __name__ == "__main__":
    main()