← Home
For problem statement at 0-999/200-299/220-229/223/problemE.txt this is a correct solution, but verifier at 0-999/200-299/220-229/223/verifierE.go ends with case 1 failed: runtime error: exit status 2
panic: runtime error: index out of range [-1]

goroutine 1 [running]:
main.main()
	/tmp/build-1482186070/solution.go:197 +0x16b4

exit status 1 can you fix the verifier? package main

import (
	"bytes"
	"fmt"
	"io"
	"math/big"
	"os"
	"sort"
	"strconv"
)

type Edge struct {
	to  int
	id  int
	dir int
}

var buffer []byte
var pos int

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

var area_b, term1, term2, xu, yv, xv, yu *big.Int

func initBig() {
	area_b = new(big.Int)
	term1 = new(big.Int)
	term2 = new(big.Int)
	xu = new(big.Int)
	yv = new(big.Int)
	xv = new(big.Int)
	yu = new(big.Int)
}

func faceAreaSign(edges []int, u_of_dir, v_of_dir []int, x, y []int64) int {
	area_b.SetInt64(0)
	for _, e := range edges {
		u := u_of_dir[e]
		v := v_of_dir[e]
		xu.SetInt64(x[u])
		yv.SetInt64(y[v])
		xv.SetInt64(x[v])
		yu.SetInt64(y[u])
		term1.Mul(xu, yv)
		term2.Mul(xv, yu)
		area_b.Add(area_b, term1.Sub(term1, term2))
	}
	return area_b.Sign()
}

func polyAreaSign(nodes []int, x, y []int64) int {
	area_b.SetInt64(0)
	k := len(nodes)
	for i := 0; i < k; i++ {
		u := nodes[i]
		v := nodes[(i+1)%k]
		xu.SetInt64(x[u])
		yv.SetInt64(y[v])
		xv.SetInt64(x[v])
		yu.SetInt64(y[u])
		term1.Mul(xu, yv)
		term2.Mul(xv, yu)
		area_b.Add(area_b, term1.Sub(term1, term2))
	}
	return area_b.Sign()
}

func half(dx, dy int64) int {
	if dy > 0 || (dy == 0 && dx > 0) {
		return 1
	}
	return 2
}

func main() {
	buffer, _ = io.ReadAll(os.Stdin)
	if len(buffer) == 0 {
		return
	}

	n := nextInt()
	m := nextInt()

	adj := make([][]Edge, n+1)
	for i := 0; i < m; i++ {
		u := nextInt()
		v := nextInt()
		adj[u] = append(adj[u], Edge{v, i, 0})
		adj[v] = append(adj[v], Edge{u, i, 1})
	}

	x := make([]int64, n+1)
	y := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		x[i] = int64(nextInt())
		y[i] = int64(nextInt())
	}

	for i := 1; i <= n; i++ {
		u := i
		sort.Slice(adj[u], func(j, k int) bool {
			e1 := adj[u][j]
			e2 := adj[u][k]
			dx1 := x[e1.to] - x[u]
			dy1 := y[e1.to] - y[u]
			dx2 := x[e2.to] - x[u]
			dy2 := y[e2.to] - y[u]

			h1 := half(dx1, dy1)
			h2 := half(dx2, dy2)
			if h1 != h2 {
				return h1 < h2
			}
			cross := dx1*dy2 - dx2*dy1
			return cross > 0
		})
	}

	pos_in_adj := make([]int, 2*m)
	u_of_dir_edge := make([]int, 2*m)
	v_of_dir_edge := make([]int, 2*m)
	for i := 1; i <= n; i++ {
		for k, e := range adj[i] {
			dir_edge := 2*e.id + e.dir
			pos_in_adj[dir_edge] = k
			u_of_dir_edge[dir_edge] = i
			v_of_dir_edge[dir_edge] = e.to
		}
	}

	initBig()

	visited := make([]bool, 2*m)
	type Face struct {
		edges []int
	}
	faces := []Face{}

	for i := 0; i < 2*m; i++ {
		if !visited[i] {
			curr := i
			face_edges := []int{}
			for {
				visited[curr] = true
				face_edges = append(face_edges, curr)

				v := v_of_dir_edge[curr]
				rev := curr ^ 1
				p := pos_in_adj[rev]
				next_idx := (p + 1) % len(adj[v])
				next_e := adj[v][next_idx]
				curr = 2*next_e.id + next_e.dir

				if curr == i {
					break
				}
			}
			faces = append(faces, Face{face_edges})
		}
	}

	f_out := -1
	for f := 0; f < len(faces); f++ {
		if faceAreaSign(faces[f].edges, u_of_dir_edge, v_of_dir_edge, x, y) < 0 {
			f_out = f
			break
		}
	}

	face_of_dir := make([]int, 2*m)
	for f, face := range faces {
		for _, e := range face.edges {
			face_of_dir[e] = f
		}
	}

	visited_face := make([]bool, len(faces))
	visited_face[f_out] = true
	queue := []int{f_out}
	parent_edge := make([]int, len(faces))
	for i := range parent_edge {
		parent_edge[i] = -1
	}

	post_order := make([]int, 0, len(faces))

	for len(queue) > 0 {
		curr_f := queue[0]
		queue = queue[1:]
		post_order = append(post_order, curr_f)

		for _, e := range faces[curr_f].edges {
			neighbor := face_of_dir[e^1]
			if !visited_face[neighbor] {
				visited_face[neighbor] = true
				parent_edge[neighbor] = e ^ 1
				queue = append(queue, neighbor)
			}
		}
	}

	g_prime := make([]int64, 2*m)
	for i := len(post_order) - 1; i >= 1; i-- {
		f := post_order[i]
		p_edge := parent_edge[f]
		sum := int64(0)
		for _, e := range faces[f].edges {
			if e != p_edge {
				sum += g_prime[e]
			}
		}
		W := int64(len(faces[f].edges) - 2)
		val := W - sum
		g_prime[p_edge] = val
		g_prime[p_edge^1] = -val
	}

	edge_id_map := make(map[uint64]int)
	for i := 0; i < 2*m; i++ {
		u := u_of_dir_edge[i]
		v := v_of_dir_edge[i]
		edge_id_map[uint64(u)<<32|uint64(v)] = i
	}

	q := nextInt()
	var outBuf bytes.Buffer
	for i := 0; i < q; i++ {
		k := nextInt()
		a := make([]int, k)
		for j := 0; j < k; j++ {
			a[j] = nextInt()
		}

		edges := make([]int, k)
		for j := 0; j < k; j++ {
			u := a[j]
			v := a[(j+1)%k]
			edges[j] = edge_id_map[uint64(u)<<32|uint64(v)]
		}

		sign := polyAreaSign(a, x, y)

		S_given := int64(0)
		for j := 0; j < k; j++ {
			S_given += g_prime[edges[j]]
		}

		S_ccw := S_given
		if sign < 0 {
			S_ccw = -S_given
		}

		V_in := (int64(2) + int64(k) + S_ccw) / 2
		outBuf.WriteString(strconv.FormatInt(V_in, 10))
		if i < q-1 {
			outBuf.WriteByte(' ')
		}
	}

	fmt.Println(outBuf.String())
}