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())
}