← Home
For problem statement at 0-999/0-99/40-49/45/problemF.txt this is a correct solution, but verifier at 0-999/0-99/40-49/45/verifierF.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
)

type DSU struct {
	parent []int
}

func NewDSU(maxIdx int) *DSU {
	p := make([]int, maxIdx+2)
	for i := 0; i <= maxIdx+1; i++ {
		p[i] = i
	}
	return &DSU{p}
}

func (d *DSU) Find(i int) int {
	if d.parent[i] == i {
		return i
	}
	d.parent[i] = d.Find(d.parent[i])
	return d.parent[i]
}

func (d *DSU) Remove(i int) {
	d.parent[i] = d.Find(i + 1)
}

type State struct {
	t, i, b, d int
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max3(a, b, c int) int {
	return max(a, max(b, c))
}

func ceilDiv2(x int) int {
	if x >= 0 {
		return (x + 1) / 2
	}
	return x / 2
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var m, n int
	if _, err := fmt.Fscan(reader, &m, &n); err != nil {
		return
	}

	queue := make([]State, 0, 600005)

	dsuM0 := NewDSU(m)
	dsuM1 := NewDSU(m)
	dsuG0 := NewDSU(m)
	dsuG1 := NewDSU(m)
	dsuZ0 := NewDSU(m)
	dsuZ1 := NewDSU(m)

	dsuM0.Remove(m)
	queue = append(queue, State{0, m, 0, 0})

	head := 0
	for head < len(queue) {
		curr := queue[head]
		head++
		t, i, b, d := curr.t, curr.i, curr.b, curr.d

		if b == 0 {
			if t == 0 {
				w := i
				L := max(0, w-n)
				R := min(w-1, m)
				if L <= R {
					for v := dsuM1.Find(L); v <= R; v = dsuM1.Find(v) {
						dsuM1.Remove(v)
						queue = append(queue, State{0, v, 1, d + 1})
					}
				}

				L = max(1, ceilDiv2(m+w-n))
				R = min(m-1, w)
				if L <= R {
					for v := dsuG1.Find(L); v <= R; v = dsuG1.Find(v) {
						dsuG1.Remove(v)
						queue = append(queue, State{1, v, 1, d + 1})
					}
				}

				L = max3(0, w+m-n, w-m)
				R = min(m, w)
				if L <= R {
					for v := dsuZ1.Find(L); v <= R; v = dsuZ1.Find(v) {
						dsuZ1.Remove(v)
						if v == 0 {
							fmt.Println(d + 1)
							return
						}
						queue = append(queue, State{2, v, 1, d + 1})
					}
				}
			} else if t == 1 {
				g := i
				L := max(1, g-n/2)
				R := min(m-1, g-1)
				if L <= R {
					for v := dsuG1.Find(L); v <= R; v = dsuG1.Find(v) {
						dsuG1.Remove(v)
						queue = append(queue, State{1, v, 1, d + 1})
					}
				}

				L = max(0, 2*g-n)
				R = min(m, g)
				if L <= R {
					for v := dsuZ1.Find(L); v <= R; v = dsuZ1.Find(v) {
						dsuZ1.Remove(v)
						if v == 0 {
							fmt.Println(d + 1)
							return
						}
						queue = append(queue, State{2, v, 1, d + 1})
					}
				}
			} else if t == 2 {
				w := i
				L := max(0, w-n)
				R := min(m, w-1)
				if L <= R {
					for v := dsuZ1.Find(L); v <= R; v = dsuZ1.Find(v) {
						dsuZ1.Remove(v)
						if v == 0 {
							fmt.Println(d + 1)
							return
						}
						queue = append(queue, State{2, v, 1, d + 1})
					}
				}
			}
		} else {
			if t == 2 {
				w := i
				L := max(0, w+1)
				R := min(m, w+n)
				if L <= R {
					for v := dsuZ0.Find(L); v <= R; v = dsuZ0.Find(v) {
						dsuZ0.Remove(v)
						queue = append(queue, State{2, v, 0, d + 1})
					}
				}

				L = max(1, w)
				R = min(m-1, (w+n)/2)
				if L <= R {
					for v := dsuG0.Find(L); v <= R; v = dsuG0.Find(v) {
						dsuG0.Remove(v)
						queue = append(queue, State{1, v, 0, d + 1})
					}
				}

				L = max(0, w)
				R = min(m, w+n-m)
				if L <= R {
					for v := dsuM0.Find(L); v <= R; v = dsuM0.Find(v) {
						dsuM0.Remove(v)
						queue = append(queue, State{0, v, 0, d + 1})
					}
				}
			} else if t == 1 {
				g := i
				L := max(1, g+1)
				R := min(m-1, g+n/2)
				if L <= R {
					for v := dsuG0.Find(L); v <= R; v = dsuG0.Find(v) {
						dsuG0.Remove(v)
						queue = append(queue, State{1, v, 0, d + 1})
					}
				}

				L = max(0, g)
				R = min(m, 2*g+n-m)
				if L <= R {
					for v := dsuM0.Find(L); v <= R; v = dsuM0.Find(v) {
						dsuM0.Remove(v)
						queue = append(queue, State{0, v, 0, d + 1})
					}
				}
			} else if t == 0 {
				w := i
				L := max(0, w+1)
				R := min(m, w+n)
				if L <= R {
					for v := dsuM0.Find(L); v <= R; v = dsuM0.Find(v) {
						dsuM0.Remove(v)
						queue = append(queue, State{0, v, 0, d + 1})
					}
				}
			}
		}
	}

	fmt.Println("-1")
}