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

Envío 6363

Problema 0xb0 - Implementar una cola de prioridad

  • Autor: Ikerlb
  • Fecha: 2022-06-27 05:44:19 UTC (Hace casi 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.005 s 10 KBi
#2
Correcto
0.006 s 4 KBi
#3
Correcto
0.003 s 4 KBi
#4
Correcto
0.005 s 22 KBi
#5
Correcto
0.003 s 4 KBi
#6
Error en tiempo de ejecución (NZEC)
Exited with error status 137
run: line 1:     3 Killed                  ./main
0.377 s 125 KBi
#7
Error en tiempo de ejecución (NZEC)
Exited with error status 137
run: line 1:     3 Killed                  ./main
0.109 s 125 KBi
#8
Error en tiempo de ejecución (NZEC)
Exited with error status 137
run: line 1:     3 Killed                  ./main
0.102 s 125 KBi
#9
Error en tiempo de ejecución (NZEC)
Exited with error status 137
run: line 1:     3 Killed                  ./main
0.106 s 125 KBi
#10
Correcto
0.261 s 13 KBi
#11
Correcto
0.123 s 11 KBi
#12
Error en tiempo de ejecución (NZEC)
Exited with error status 137
run: line 1:     3 Killed                  ./main
0.13 s 125 KBi
#13
Error en tiempo de ejecución (NZEC)
Exited with error status 137
run: line 1:     3 Killed                  ./main
0.494 s 125 KBi
#14
Error en tiempo de ejecución (NZEC)
Exited with error status 137
run: line 1:     3 Killed                  ./main
0.161 s 125 KBi
#15
Error en tiempo de ejecución (NZEC)
Exited with error status 137
run: line 1:     3 Killed                  ./main
0.141 s 125 KBi
#16
Error en tiempo de ejecución (NZEC)
Exited with error status 137
run: line 1:     3 Killed                  ./main
0.197 s 125 KBi
#17
Error en tiempo de ejecución (NZEC)
Exited with error status 137
run: line 1:     3 Killed                  ./main
0.269 s 125 KBi
Puntos totales: 42 / 100

Código

package main

import (
    "fmt"
    "os"
    "bufio"
    "strconv"
    "strings"
)

type Node struct {
    S string;
    P int;
}

type Heap struct {
    Tree []Node;
}

func NewHeap() Heap {
    arr := make([]Node, 0)
    return Heap {
        Tree: arr,
    }
}

func Left(i int) int {
    return i >> 1 + 1
}

func Right(i int) int {
    return i >> 1 + 2
}

func Parent(i int) int {
    return (i - 1) >> 1
}

func Cmp(n1, n2 Node) int {
    if n1.P < n2.P {
        return -1
    } else if n1.P > n2.P {
        return 1
    } else {
        return strings.Compare(n1.S, n2.S)
    }
}

func (h *Heap) HeapifyDown(i int) {
    l := Left(i)
    r := Right(i)
    smallest := i
    
    if l < len(h.Tree) && Cmp(h.Tree[l], h.Tree[i]) < 0 {
        smallest = l
    }
    if r < len(h.Tree) && Cmp(h.Tree[r], h.Tree[smallest]) < 0 {
        smallest = r
    }
    if smallest != i {
        h.Tree[i], h.Tree[smallest] = h.Tree[smallest], h.Tree[i]
        h.HeapifyDown(smallest)
    }
}

func (h *Heap) Pop() Node {
    var res Node
    last := len(h.Tree) - 1
    h.Tree[last], h.Tree[0] = h.Tree[0], h.Tree[last]
    // TODO CHECK!
    h.Tree, res = h.Tree[0:last], h.Tree[last]
    h.HeapifyDown(0)
    return res
}

func (h *Heap) HeapifyUp(i int) {
    for i != 0 {
        p := Parent(i)
        if Cmp(h.Tree[p], h.Tree[i]) <= 0 {
            break
        }
        h.Tree[p], h.Tree[i] = h.Tree[i], h.Tree[p]
        i = p
    }
}

func (h *Heap) Add(elem Node) {
    h.Tree = append(h.Tree, elem)
    h.HeapifyUp(len(h.Tree) - 1)
}

func (h *Heap) Peek() Node{
    return h.Tree[0]
}

func main() {
    var p int
    var s, line, dummy string
    sc := bufio.NewScanner(os.Stdin)
    
    sc.Scan()
    ops, _ := strconv.Atoi(sc.Text())

    h := NewHeap()

    for o := 0; o < ops; o += 1 {
        sc.Scan()
        line = sc.Text() 
        if line[0] == 'I' {
            fmt.Sscanf(line, "%s %s %d", &dummy, &s, &p)
            n := Node{
                S: s,
                P: -p,
            }
            h.Add(n)
        } else if line[0] == 'G' {
            fmt.Println(h.Peek().S)

        } else {
            h.Pop()
        }
    }
}