← Home
For problem statement at 0-999/700-799/750-759/750/problemE.txt this is a correct solution, but verifier at 0-999/700-799/750-759/750/verifierE.go ends with all tests passed can you fix the verifier? package main

import (
	"io"
	"os"
	"strconv"
)

const INF int32 = 1 << 29

type Mat struct {
	a [25]int32
}

type Vec [5]int32

var data []byte
var ptr int

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

func nextToken() []byte {
	for ptr < len(data) && data[ptr] <= ' ' {
		ptr++
	}
	start := ptr
	for ptr < len(data) && data[ptr] > ' ' {
		ptr++
	}
	return data[start:ptr]
}

func identity() Mat {
	var m Mat
	for i := 0; i < 5; i++ {
		base := i * 5
		for j := i; j < 5; j++ {
			if i == j {
				m.a[base+j] = 0
			} else {
				m.a[base+j] = INF
			}
		}
	}
	return m
}

func charMat(c byte, id Mat) Mat {
	m := id
	switch c {
	case '2':
		m.a[0] = 1
		m.a[1] = 0
	case '0':
		m.a[6] = 1
		m.a[7] = 0
	case '1':
		m.a[12] = 1
		m.a[13] = 0
	case '6':
		m.a[18] = 1
		m.a[24] = 1
	case '7':
		m.a[18] = 1
		m.a[19] = 0
	}
	return m
}

func mul(x, y Mat) Mat {
	var z Mat
	for i := 0; i < 5; i++ {
		base := i * 5
		for k := i; k < 5; k++ {
			best := INF
			for j := i; j <= k; j++ {
				v := x.a[base+j] + y.a[j*5+k]
				if v < best {
					best = v
				}
			}
			z.a[base+k] = best
		}
	}
	return z
}

func mulRow(v Vec, m Mat) Vec {
	var u Vec
	for k := 0; k < 5; k++ {
		best := INF
		for j := 0; j <= k; j++ {
			val := v[j] + m.a[j*5+k]
			if val < best {
				best = val
			}
		}
		u[k] = best
	}
	return u
}

func mulCol(m Mat, v Vec) Vec {
	var u Vec
	for i := 0; i < 5; i++ {
		base := i * 5
		best := INF
		for j := i; j < 5; j++ {
			val := m.a[base+j] + v[j]
			if val < best {
				best = val
			}
		}
		u[i] = best
	}
	return u
}

func main() {
	data, _ = io.ReadAll(os.Stdin)
	n := nextInt()
	q := nextInt()
	s := nextToken()

	id := identity()
	var mats [10]Mat
	for d := byte('0'); d <= '9'; d++ {
		mats[d-'0'] = charMat(d, id)
	}

	size := 1
	for size < n {
		size <<= 1
	}

	tree := make([]Mat, size<<1)
	for i := size; i < size<<1; i++ {
		tree[i] = id
	}
	for i := 0; i < n; i++ {
		tree[size+i] = mats[s[i]-'0']
	}
	for i := size - 1; i > 0; i-- {
		tree[i] = mul(tree[i<<1], tree[i<<1|1])
	}

	startV := Vec{0, INF, INF, INF, INF}
	endV := Vec{INF, INF, INF, INF, 0}

	out := make([]byte, 0, q*8)
	for ; q > 0; q-- {
		l := nextInt() - 1
		r := nextInt() - 1
		l += size
		r += size + 1
		left := startV
		right := endV
		for l < r {
			if l&1 == 1 {
				left = mulRow(left, tree[l])
				l++
			}
			if r&1 == 1 {
				r--
				right = mulCol(tree[r], right)
			}
			l >>= 1
			r >>= 1
		}
		ans := INF
		for i := 0; i < 5; i++ {
			v := left[i] + right[i]
			if v < ans {
				ans = v
			}
		}
		if ans >= INF/2 {
			out = append(out, '-', '1', '\n')
		} else {
			out = strconv.AppendInt(out, int64(ans), 10)
			out = append(out, '\n')
		}
	}

	os.Stdout.Write(out)
}