← Home
For problem statement at 0-999/900-999/920-929/921/problem01.txt this is a correct solution, but verifier at 0-999/900-999/920-929/921/verifier01.go ends with reference runtime error on test 1: exec: "ref92101.bin": executable file not found in $PATH
Input used:
<empty>

exit status 1 can you fix the verifier? ```go
package main

import (
	"container/heap"
	"fmt"
	"io"
	"os"
	"strings"
)

var data []byte
var pos int

func nextString() string {
	for pos < len(data) && data[pos] <= ' ' {
		pos++
	}
	if pos >= len(data) {
		return ""
	}
	start := pos
	for pos < len(data) && data[pos] > ' ' {
		pos++
	}
	return string(data[start:pos])
}

func nextInt() int {
	for pos < len(data) && data[pos] <= ' ' {
		pos++
	}
	if pos >= len(data) {
		return 0
	}
	res := 0
	for pos < len(data) && data[pos] > ' ' {
		res = res*10 + int(data[pos]-'0')
		pos++
	}
	return res
}

type ListNode struct {
	val  uint64
	next *ListNode
}

func contains(head *ListNode, val uint64) bool {
	for head != nil {
		if head.val == val {
			return true
		}
		head = head.next
	}
	return false
}

var zKey [100005]uint64
var zDoor [100005]uint64

func initHashes() {
	var seed uint64 = 42
	next := func() uint64 {
		seed ^= seed << 13
		seed ^= seed >> 7
		seed ^= seed << 17
		return seed
	}
	for i := 0; i < 100005; i++ {
		zKey[i] = next()
		zDoor[i] = next()
	}
}

var N, M int

func getEdge(x, y int, d int, horiz, vert []int, M int) int {
	if d == 0 { // Up
		return horiz[(x-1)*M+y]
	} else if d == 1 { // Down
		return horiz[x*M+y]
	} else if d == 2 { // Left
		return vert[x*M+(y-1)]
	} else if d == 3 { // Right
		return vert[x*M+y]
	}
	return 1
}

type State struct {
	hash   uint64
	picked *ListNode
	opened *ListNode
	parent *State
	dist   uint32
	x, y   uint16
	keys   uint16
	action uint8 // 0: U, 1: D, 2: L, 3: R, 4: OU, 5: OD, 6: OL, 7: OR, 8: Take
}

type VisKey struct {
	hash uint64
	x, y uint16
	keys uint16
}

type Item struct {
	state    *State
	priority uint32
	index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].priority < pq[j].priority }
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(*Item)
	item.index = len(*pq)
	*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil
	item.index = -1
	*pq = old[0 : n-1]
	return item
}

type HItem struct {
	idx  int
	dist uint32
}
type HQueue []*HItem

func (q HQueue) Len() int           { return len(q) }
func (q HQueue) Less(i, j int) bool { return q[i].dist < q[j].dist }
func (q HQueue) Swap(i, j int)      { q[i], q[j] = q[j], q[i] }
func (q *HQueue) Push(x interface{}) {
	*q = append(*q, x.(*HItem))
}
func (q *HQueue) Pop() interface{} {
	old := *q
	n := len(old)
	x := old[n-1]
	*q = old[0 : n-1]
	return x
}

func printPath(curr *State) {
	var actions []uint8
	for curr.parent != nil {
		actions = append(actions, curr.action)
		curr = curr.parent
	}

	for i, j := 0, len(actions)-1; i < j; i, j = i+1, j-1 {
		actions[i], actions[j] = actions[j], actions[i]
	}

	cmds := []string{
		"move-up", "move-down", "move-left", "move-right",
		"open-up", "open-down", "open-left", "open-right",
		"take",
	}

	var sb strings.Builder
	n := len(actions)
	for i := 0; i < n; {
		j := i
		for j < n && actions[j] == actions[i] {
			j++
		}
		count := j - i
		cmdStr := cmds[actions[i]]
		if count >= 4 {
			if sb.Len() > 0 {
				sb.WriteString(" ")
			}
			sb.WriteString(fmt.Sprintf("for-%d %s end", count, cmdStr))
		} else {
			for k := 0; k < count; k++ {
				if sb.Len() > 0 {
					sb.WriteString(" ")
				}
				sb.WriteString(cmdStr)
			}
		}
		i = j
	}
	fmt.Println(sb.String())
}

func main() {
	input, _ := io.ReadAll(os.Stdin)
	data = input
	initHashes()

	nextString() 
	nextString() 

	N = nextInt()
	M = nextInt()
	x0 := nextInt()
	y0 := nextInt()
	C := nextInt()
	D := nextInt()
	K := nextInt()
	E := nextInt()

	horiz := make([]int, N*M)
	vert := make([]int, N*M)
	keyGrid := make([]int, N*M)
	isExit := make([]bool, N*M)
	exitsList := make([]int, 0, E)

	for i := 0; i < C; i++ {
		x1, y1, x2, y2 := nextInt(), nextInt(), nextInt(), nextInt()
		if x1 > x2 {
			x1, x2 = x2, x1
		}
		if y1 > y2 {
			y1, y2 = y2, y1
		}
		if x1 != x2 {
			horiz[x1*M+y1] = 1
		} else {
			vert[x1*M+y1] = 1
		}
	}

	for i := 0; i < D; i++ {
		x1, y1, x2, y2 := nextInt(), nextInt(), nextInt(), nextInt()
		if x1 > x2 {
			x1, x2 = x2, x1
		}
		if y1 > y2 {
			y1, y2 = y2, y1
		}
		if x1 != x2 {
			horiz[x1*M+y1] = 2 + i
		} else {
			vert[x1*M+y1] = 2 + i
		}
	}

	for i := 0; i < K; i++ {
		x, y := nextInt(), nextInt()
		keyGrid[x*M+y] = i + 1
	}

	for i := 0; i < E; i++ {
		x, y := nextInt(), nextInt()
		isExit[x*M+y] = true
		exitsList = append(exitsList, x*M+y)
	}

	h := make([]uint32, N*M)
	for i := 0; i < N*M; i++ {
		h[i] = 1e9
	}

	hq := &HQueue{}
	heap.Init(hq)
	for _, ex := range exitsList {
		h[ex] = 0
		heap.Push(hq, &HItem{ex, 0})
	}

	dx := []int{-1, 1, 0, 0}
	dy := []int{0, 0, -1, 1}

	for hq.Len() > 0 {
		curr := heap.Pop(hq).(*HItem)
		if curr.dist > h[curr.idx] {
			continue
		}
		cx := curr.idx / M
		cy := curr.idx % M
		for d := 0; d < 4; d++ {
			nx := cx + dx[d]
			ny := cy + dy[d]
			if nx < 0 || nx >= N || ny < 0 || ny >= M {
				continue
			}
			edge := getEdge(cx, cy, d, horiz, vert, M)
			if edge == 1 {
				continue
			}
			cost := uint32(1)
			if edge >= 2 {
				cost = 2
			}
			nidx := nx*M + ny
			if h[curr.idx]+cost < h[nidx] {
				h[nidx] = h[curr.idx] + cost
				heap.Push(hq, &HItem{nidx, h[nidx]})
			}
		}
	}

	startState := &State{
		x: uint16(x0), y: uint16(y0),
		keys: 0, dist: 0, hash: 0,
		picked: nil, opened: nil, parent: nil,
	}

	pq := make(PriorityQueue, 0)
	heap.Init(&pq)
	heap.Push(&pq, &Item{
		state:    startState,
		priority: h[x0*M+y0],
	})

	bestDist := make(map[VisKey]uint32)
	bestDist[VisKey{0, uint16(x0), uint16(y0), 0}] = 0

	pushIfBetter := func(v *State) {
		vk := VisKey{
			hash: v.hash,
			x:    v.x,
			y:    v.y,
			keys: v.keys,
		}
		if d, ok := bestDist[vk]; ok && d <= v.dist {
			return
		}
		bestDist[vk] = v.dist
		heap.Push(&pq, &Item{
			state:    v,
			priority: v.dist + h[int(v.x)*M+int(v.y)],
		})
	}

	for pq.Len() > 0 {
		currItem := heap.Pop(&pq).(*Item)
		curr := currItem.state

		if isExit[int(curr.x)*M+int(curr.y)] {
			printPath(curr)
			return
		}

		if keyID := keyGrid[int(curr.x)*M+int(curr.y)]; keyID > 0 {
			id := uint64(keyID - 1)
			if !contains(curr.picked, id) {
				v := &State{
					hash:   curr.hash ^ zKey[id],
					picked: &ListNode{id, curr.picked},
					opened: curr.opened,
					parent: curr,
					dist:   curr.dist + 1,
					x:      curr.x,
					y:      curr.y,
					keys:   curr.keys + 1,
					action: 8,
				}
				pushIfBetter(v)
			}
		}

		for d := 0; d < 4; d++ {
			nx := int(curr.x) + dx[d]
			ny := int(curr.y) + dy[d]
			if nx < 0 || nx >= N || ny < 0 || ny >= M {
				continue
			}
			edge := getEdge(int(curr.x), int(curr.y), d, horiz, vert, M)
			if edge == 1 {
				continue
			}
			if edge >= 2 {
				doorID := uint64(edge - 2)
				if contains(curr.opened, doorID) {
					v := &State{
						hash:   curr.hash,
						picked: curr.picked,
						opened: curr.opened,
						parent: curr,
						dist:   curr.dist + 1,
						x:      uint16(nx),
						y:      uint16(ny),
						keys:   curr.keys,
						action: uint8(d),
					}
					pushIfBetter(v)
				} else {
					if curr.keys > 0 {
						v := &State{
							hash:   curr.hash ^ zDoor[doorID],
							picked: curr.picked,
							opened: &ListNode{doorID, curr.opened},
							parent: curr,
							dist:   curr.dist + 1,
							x:      curr.x,
							y:      curr.y,
							keys:   curr.keys - 1,
							action: uint8(4 + d),
						}
						pushIfBetter(v)
					}
				}
			} else {
				v := &State{
					hash:   curr.hash,
					picked: curr.picked,
					opened: curr.opened,
					parent: curr,
					dist:   curr.dist + 1,
					x:      uint16(nx),
					y:      uint16(ny),
					keys:   curr.keys,
					action: uint8(d),
				}
				pushIfBetter(v)
			}
		}
	}
	fmt.Println("terminate")
}
```