For problem statement at 0-999/200-299/240-249/241/problemF.txt this is a correct solution, but verifier at 0-999/200-299/240-249/241/verifierF.go ends with test 1: runtime error: runtime error: exit status 2
panic: runtime error: index out of range [-1]
goroutine 1 [running]:
main.main()
/tmp/build-3735059102/solution.go:253 +0x2280
exit status 1 can you fix the verifier? package main
import (
"bufio"
"container/heap"
"fmt"
"os"
"sort"
)
type Point struct {
r, c int
}
type Segment struct {
a, b int
cells []Point
vals []int
pref []int
}
type Edge struct {
to, sid int
w int64
}
type Item struct {
d int64
id int
}
type MinHeap []Item
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool {
if h[i].d != h[j].d {
return h[i].d < h[j].d
}
return h[i].id < h[j].id
}
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
*h = append(*h, x.(Item))
}
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
var (
m, n int
grid [][]byte
junction [26]Point
present [26]bool
segIdAt [][]int
idxAt [][]int
segments []Segment
adj [26][]Edge
endSegId int
endIdx int
startSegId int
startIdx int
)
func isDigit(ch byte) bool {
return ch >= '1' && ch <= '9'
}
func isJunction(ch byte) bool {
return ch >= 'a' && ch <= 'z'
}
func inBounds(r, c int) bool {
return r >= 0 && r < m && c >= 0 && c < n
}
func doMove(cur *Point, next Point, cost int, rem *int64) (bool, Point) {
if *rem < int64(cost) {
return true, *cur
}
*rem -= int64(cost)
*cur = next
if *rem == 0 {
return true, *cur
}
return false, Point{}
}
func walkStreetToEndpoint(segId, idx, endpoint int, cur *Point, rem *int64) (bool, Point) {
seg := segments[segId]
t := len(seg.cells)
if endpoint == seg.a {
for i := idx; i >= 0; i-- {
next := junction[seg.a]
if i > 0 {
next = seg.cells[i-1]
}
if done, ans := doMove(cur, next, seg.vals[i], rem); done {
return true, ans
}
}
} else {
for i := idx; i < t; i++ {
next := junction[seg.b]
if i+1 < t {
next = seg.cells[i+1]
}
if done, ans := doMove(cur, next, seg.vals[i], rem); done {
return true, ans
}
}
}
return false, Point{}
}
func walkFullSegment(segId, from int, cur *Point, rem *int64) (bool, Point) {
seg := segments[segId]
t := len(seg.cells)
if from == seg.a {
if done, ans := doMove(cur, seg.cells[0], 1, rem); done {
return true, ans
}
for i := 0; i < t; i++ {
next := junction[seg.b]
if i+1 < t {
next = seg.cells[i+1]
}
if done, ans := doMove(cur, next, seg.vals[i], rem); done {
return true, ans
}
}
} else {
if done, ans := doMove(cur, seg.cells[t-1], 1, rem); done {
return true, ans
}
for i := t - 1; i >= 0; i-- {
next := junction[seg.a]
if i-1 >= 0 {
next = seg.cells[i-1]
}
if done, ans := doMove(cur, next, seg.vals[i], rem); done {
return true, ans
}
}
}
return false, Point{}
}
func walkEndpointToStreet(segId, endpoint, idx int, cur *Point, rem *int64) (bool, Point) {
seg := segments[segId]
t := len(seg.cells)
if endpoint == seg.a {
if done, ans := doMove(cur, seg.cells[0], 1, rem); done {
return true, ans
}
for i := 0; i < idx; i++ {
if done, ans := doMove(cur, seg.cells[i+1], seg.vals[i], rem); done {
return true, ans
}
}
} else {
if done, ans := doMove(cur, seg.cells[t-1], 1, rem); done {
return true, ans
}
for i := t - 1; i > idx; i-- {
if done, ans := doMove(cur, seg.cells[i-1], seg.vals[i], rem); done {
return true, ans
}
}
}
return false, Point{}
}
func betterTransition(newPar int, newType byte, newEdge int, oldPar int, oldType byte, oldEdge int) bool {
if oldPar == -2 {
return true
}
if newPar != oldPar {
return newPar < oldPar
}
if newType != oldType {
return newType < oldType
}
return newEdge < oldEdge
}
func main() {
in := bufio.NewReaderSize(os.Stdin, 1<<20)
out := bufio.NewWriterSize(os.Stdout, 1<<20)
defer out.Flush()
var k int64
fmt.Fscan(in, &m, &n, &k)
grid = make([][]byte, m)
for i := 0; i < m; i++ {
var s string
fmt.Fscan(in, &s)
grid[i] = []byte(s)
for j := 0; j < n; j++ {
if isJunction(grid[i][j]) {
id := int(grid[i][j] - 'a')
present[id] = true
junction[id] = Point{i, j}
}
}
}
var rs, cs, re, ce int
var seq string
fmt.Fscan(in, &rs, &cs, &seq, &re, &ce)
rs--
cs--
re--
ce--
segIdAt = make([][]int, m)
idxAt = make([][]int, m)
for i := 0; i < m; i++ {
segIdAt[i] = make([]int, n)
idxAt[i] = make([]int, n)
for j := 0; j < n; j++ {
segIdAt[i][j] = -1
idxAt[i][j] = -1
}
}
dirs := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
for id := 0; id < 26; id++ {
if !present[id] {
continue
}
p := junction[id]
for _, d := range dirs {
nr, nc := p.r+d[0], p.c+d[1]
if !inBounds(nr, nc) || !isDigit(grid[nr][nc]) || segIdAt[nr][nc] != -1 {
continue
}
sid := len(segments)
var cells []Point
var vals []int
cr, cc := nr, nc
for {
cells = append(cells, Point{cr, cc})
vals = append(vals, int(grid[cr][cc]-'0'))
segIdAt[cr][cc] = sid
idxAt[cr][cc] = len(cells) - 1
nnr, nnc := cr+d[0], cc+d[1]
if isDigit(grid[nnr][nnc]) {
cr, cc = nnr, nnc
continue
}
bid := int(grid[nnr][nnc] - 'a')
pref := make([]int, len(vals)+1)
for i, v := range vals {
pref[i+1] = pref[i] + v
}
segments = append(segments, Segment{
a: id,
b: bid,
cells: cells,
vals: vals,
pref: pref,
})
w := int64(1 + pref[len(vals)])
adj[id] = append(adj[id], Edge{to: bid, sid: sid, w: w})
adj[bid] = append(adj[bid], Edge{to: id, sid: sid, w: w})
break
}
}
}
for i := 0; i < 26; i++ {
sort.Slice(adj[i], func(a, b int) bool {
if adj[i][a].to != adj[i][b].to {
return adj[i][a].to < adj[i][b].to
}
return adj[i][a].sid < adj[i][b].sid
})
}
startSegId = segIdAt[rs][cs]
startIdx = idxAt[rs][cs]
endSegId = segIdAt[re][ce]
endIdx = idxAt[re][ce]
req := make([]int, len(seq))
for i := range seq {
req[i] = int(seq[i] - 'a')
}
q := len(req)
numStates := (q+1)*26 + 2
source := (q + 1) * 26
sink := source + 1
const INF int64 = 1 << 60
dist := make([]int64, numStates)
parent := make([]int, numStates)
ptype := make([]byte, numStates)
pedge := make([]int, numStates)
for i := 0; i < numStates; i++ {
dist[i] = INF
parent[i] = -2
pedge[i] = -1
}
dist[source] = 0
parent[source] = -1
var h MinHeap
relax := func(from, to int, nd int64, tp byte, ed int) {
if nd < dist[to] || (nd == dist[to] && betterTransition(from, tp, ed, parent[to], ptype[to], pedge[to])) {
dist[to] = nd
parent[to] = from
ptype[to] = tp
pedge[to] = ed
heap.Push(&h, Item{d: nd, id: to})
}
}
heap.Init(&h)
heap.Push(&h, Item{d: 0, id: source})
startSeg := segments[startSegId]
startCostA := int64(startSeg.pref[startIdx+1])
startCostB := int64(startSeg.pref[len(startSeg.cells)] - startSeg.pref[startIdx])
endSeg := segments[endSegId]
endCostA := int64(1 + endSeg.pref[endIdx])
endCostB := int64(1 + endSeg.pref[len(endSeg.cells)] - endSeg.pref[endIdx+1])
for h.Len() > 0 {
it := heap.Pop(&h).(Item)
if it.d != dist[it.id] {
continue
}
if it.id == sink {
break
}
if it.id == source {
a, b := startSeg.a, startSeg.b
ca, cb := startCostA, startCostB
if a > b {
a, b = b, a
ca, cb = cb, ca
}
na := 0
if q > 0 && a == req[0] {
na = 1
}
nb := 0
if q > 0 && b == req[0] {
nb = 1
}
relax(source, na*26+a, it.d+ca, 1, -1)
relax(source, nb*26+b, it.d+cb, 1, -1)
continue
}
layer := it.id / 26
u := it.id % 26
for _, e := range adj[u] {
nlayer := layer
if nlayer < q && e.to == req[nlayer] {
nlayer++
}
to := nlayer*26 + e.to
relax(it.id, to, it.d+e.w, 2, e.sid)
}
if layer == q {
if u == endSeg.a {
relax(it.id, sink, it.d+endCostA, 3, -1)
}
if u == endSeg.b {
relax(it.id, sink, it.d+endCostB, 3, -1)
}
}
}
if k >= dist[sink] {
fmt.Fprintln(out, re+1, ce+1)
return
}
var path []int
for cur := sink; cur != -1; cur = parent[cur] {
path = append(path, cur)
if cur == source {
break
}
}
for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
path[i], path[j] = path[j], path[i]
}
curPos := Point{rs, cs}
rem := k
if rem == 0 {
fmt.Fprintln(out, curPos.r+1, curPos.c+1)
return
}
for i := 1; i < len(path); i++ {
st := path[i]
switch ptype[st] {
case 1:
endpoint := st % 26
if done, ans := walkStreetToEndpoint(startSegId, startIdx, endpoint, &curPos, &rem); done {
fmt.Fprintln(out, ans.r+1, ans.c+1)
return
}
case 2:
sid := pedge[st]
from := path[i-1] % 26
if done, ans := walkFullSegment(sid, from, &curPos, &rem); done {
fmt.Fprintln(out, ans.r+1, ans.c+1)
return
}
case 3:
endpoint := path[i-1] % 26
if done, ans := walkEndpointToStreet(endSegId, endpoint, endIdx, &curPos, &rem); done {
fmt.Fprintln(out, ans.r+1, ans.c+1)
return
}
}
}
fmt.Fprintln(out, re+1, ce+1)
}