← 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 (
	"bufio"
	"fmt"
	"os"
)

const INF int32 = 1e9

type Node struct {
	mat [5][5]int32
}

var tree []Node

func multiply(A, B [5][5]int32) [5][5]int32 {
	var C [5][5]int32
	for i := 0; i < 5; i++ {
		for j := i; j < 5; j++ {
			C[i][j] = INF
			for k := i; k <= j; k++ {
				if A[i][k]+B[k][j] < C[i][j] {
					C[i][j] = A[i][k] + B[k][j]
				}
			}
		}
	}
	return C
}

func build(node, l, r int, s string) {
	if l == r {
		for i := 0; i < 5; i++ {
			for j := 0; j < 5; j++ {
				tree[node].mat[i][j] = INF
			}
			tree[node].mat[i][i] = 0
		}
		c := s[l]
		if c == '2' {
			tree[node].mat[0][0] = 1
			tree[node].mat[0][1] = 0
		} else if c == '0' {
			tree[node].mat[1][1] = 1
			tree[node].mat[1][2] = 0
		} else if c == '1' {
			tree[node].mat[2][2] = 1
			tree[node].mat[2][3] = 0
		} else if c == '7' {
			tree[node].mat[3][3] = 1
			tree[node].mat[3][4] = 0
		} else if c == '6' {
			tree[node].mat[3][3] = 1
			tree[node].mat[4][4] = 1
		}
		return
	}
	mid := (l + r) / 2
	build(2*node, l, mid, s)
	build(2*node+1, mid+1, r, s)
	tree[node].mat = multiply(tree[2*node].mat, tree[2*node+1].mat)
}

func query(node, l, r, ql, qr int) [5][5]int32 {
	if ql <= l && r <= qr {
		return tree[node].mat
	}
	mid := (l + r) / 2
	if qr <= mid {
		return query(2*node, l, mid, ql, qr)
	}
	if ql > mid {
		return query(2*node+1, mid+1, r, ql, qr)
	}
	return multiply(query(2*node, l, mid, ql, qr), query(2*node+1, mid+1, r, ql, qr))
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n, q int
	fmt.Fscan(reader, &n, &q)

	var s string
	fmt.Fscan(reader, &s)

	tree = make([]Node, 4*n)
	build(1, 0, n-1, s)

	for i := 0; i < q; i++ {
		var a, b int
		fmt.Fscan(reader, &a, &b)
		a--
		b--
		res := query(1, 0, n-1, a, b)
		ans := res[0][4]
		if ans >= INF {
			fmt.Fprintln(writer, -1)
		} else {
			fmt.Fprintln(writer, ans)
		}
	}
}