← Home
For problem statement at 1000-1999/1200-1299/1270-1279/1270/problemF.txt this is a correct solution, but verifier at 1000-1999/1200-1299/1270-1279/1270/verifierF.go ends with all tests passed can you fix the verifier? package main

import (
	"fmt"
	"io"
	"math"
	"os"
)

type HashTable struct {
	keys [524288]int32
	vals [524288]int32
	used [200005]uint32
	head int
}

func (ht *HashTable) Add(key int32) int32 {
	idx := (uint32(key) * 2654435761) & 524287
	for {
		v := ht.vals[idx]
		if v == 0 {
			ht.keys[idx] = key
			ht.vals[idx] = 1
			ht.used[ht.head] = idx
			ht.head++
			return 0
		}
		if ht.keys[idx] == key {
			ht.vals[idx] = v + 1
			return v
		}
		idx = (idx + 1) & 524287
	}
}

func (ht *HashTable) Clear() {
	for i := 0; i < ht.head; i++ {
		idx := ht.used[i]
		ht.keys[idx] = 0
		ht.vals[idx] = 0
	}
	ht.head = 0
}

func main() {
	data, err := io.ReadAll(os.Stdin)
	if err != nil {
		return
	}
	var buf []byte
	for _, b := range data {
		if b == '0' || b == '1' {
			buf = append(buf, b)
		}
	}
	n := len(buf)
	if n == 0 {
		return
	}

	p := make([]int32, n+1)
	pos := make([]int, 0)
	pos = append(pos, 0)
	for i := 0; i < n; i++ {
		p[i+1] = p[i]
		if buf[i] == '1' {
			p[i+1]++
			pos = append(pos, i+1)
		}
	}
	pos = append(pos, n+1)
	m := len(pos) - 2

	B := int(math.Sqrt(float64(n)))
	var ans int64

	ht := &HashTable{}

	for k := 1; k <= B; k++ {
		for i := 0; i <= n; i++ {
			val := int32(i) - int32(k)*p[i]
			ans += int64(ht.Add(val))
		}
		ht.Clear()
	}

	for c := 1; c*B < n; c++ {
		Bc := B * c
		for i := 1; i <= m-c+1; i++ {
			l_min := pos[i-1] + 1
			l_max := pos[i]
			r_min := pos[i+c-1]
			r_max := pos[i+c] - 1

			for l := l_min; l <= l_max; l++ {
				R_min := r_min
				if l+Bc > R_min {
					R_min = l + Bc
				}
				if R_min <= r_max {
					M := (l - 1) % c
					X := R_min
					rem := X % c
					if rem != M {
						diff := M - rem
						if diff < 0 {
							diff += c
						}
						X += diff
					}
					if X <= r_max {
						ans += int64((r_max-X)/c + 1)
					}
				}
			}
		}
	}

	fmt.Println(ans)
}