█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 6361

Problema 0xb0 - Implementar una cola de prioridad

  • Autor: Ikerlb
  • Fecha: 2022-06-27 04:19:32 UTC (Hace casi 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.094 s 11 KBi
#2
Correcto
0.042 s 11 KBi
#3
Correcto
0.156 s 11 KBi
#4
Correcto
0.107 s 11 KBi
#5
Correcto
0.044 s 11 KBi
#6
Correcto
0.114 s 11 KBi
#7
Correcto
0.048 s 11 KBi
#8
Correcto
0.051 s 11 KBi
#9
Correcto
0.057 s 11 KBi
#10
Correcto
0.724 s 23 KBi
#11
Correcto
0.863 s 24 KBi
#12
Incorrecto
1.154 s 17 KBi
#13
Incorrecto
0.975 s 23 KBi
#14
Incorrecto
1.203 s 23 KBi
#15
Incorrecto
0.466 s 17 KBi
#16
Incorrecto
0.955 s 24 KBi
#17
Incorrecto
1.206 s 24 KBi
Puntos totales: 65 / 100

Código

from functools import total_ordering

@total_ordering
class Node:
    def __init__(self, s, p):
        self.s = s
        self.p = -p

    def __lt__(self, other):
        if self.p < other.p:
            return True
        elif self.p > other.p:
            return False
        return self.s < other.s
    
    def __eq__(self, other):
        return self.s == other.s and self.p == other.p

    def __repr__(self):
        return f"{self.s}"

class Heap:
    def __init__(self, n):
        self.tree = [None for _ in range(n + 1)]
        self.n = 0 

    def right(self, i):
        return (i << 1) + 1

    def left(self, i):
        return (i << 1) + 2

    def parent(self, i):
        return i >> 1

    def __len__(self):
        return self.n

    def heapify_down(self, i):
        l = self.left(i)
        r = self.right(i)
        children = [c for c in [l, r] if c < self.n]
        if all(self.tree[i] < self.tree[c] for c in children):
            return     
        sm = min(children, key = lambda x: self.tree[x])
        self.tree[sm], self.tree[i] = self.tree[i], self.tree[sm]
        self.heapify_down(sm)

    def heapify_up(self, i):
        while i != 0:
            p = self.parent(i)
            #print(f"{i=} {p=}")
            if self.tree[p] <= self.tree[i]:
                break    
            self.tree[p], self.tree[i] = self.tree[i], self.tree[p]
            i = p

    def add(self, elem):
        i = self.n
        self.tree[i] = elem
        self.n += 1
        self.heapify_up(i)


    def pop(self): 
        self.n -= 1 
        res = self.tree[0]
        self.tree[self.n], self.tree[0] = self.tree[0], self.tree[self.n] 
        self.tree[self.n] = None
        self.heapify_down(0)
        return res 

    def peek(self):
        return self.tree[0]

h = Heap(1_000_000)
num_lines = int(input())
for _ in range(num_lines):
    line = input()
    if line[0] == "I":
        _, s, p = line.split(" ")
        n = Node(s, int(p))
        h.add(n)
    elif line[0] == "G":
        n = h.peek()
        print(n)
    else:
        h.pop()