← Home
For problem statement at 2000-2999/2000-2099/2070-2079/2070/problemE.txt this is a correct solution, but verifier at 2000-2999/2000-2099/2070-2079/2070/verifierE.go ends with All 78 tests passed. can you fix the verifier? ```go
package main

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

func main() {
	// Configure fast I/O
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

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

	// Based on game analysis:
	// Alice (Player 1) removes "00" (two 0s).
	// Bob (Player 2) removes "01", "10", or "11" (at least one 1).
	// Under optimal play, Alice wins a substring if:
	// cnt0 >= 3*cnt1 + 2  OR  cnt0 == 3*cnt1 - 1
	// where cnt0 is count of '0's and cnt1 is count of '1's.
	//
	// We can transform this into a weighted sum problem.
	// Assign weight 1 to '0' and -3 to '1'.
	// Let S be the sum of weights in the substring.
	// S = 1*cnt0 + (-3)*cnt1 = cnt0 - 3*cnt1.
	// Conditions become:
	// 1) cnt0 - 3*cnt1 >= 2  => S >= 2
	// 2) cnt0 - 3*cnt1 == -1 => S == -1
	//
	// We need to count pairs (l, r) such that P[r] - P[l-1] satisfies these conditions.
	// P[r] - P[l-1] >= 2  => P[l-1] <= P[r] - 2
	// P[r] - P[l-1] == -1 => P[l-1] == P[r] + 1

	// Max value of P[i] is N (all 0s), Min value is -3N (all 1s).
	// We use an offset to map values to positive indices for a Fenwick Tree (BIT).
	// Range roughly -3N to N. Size ~ 4N.
	offset := 3*n + 5
	limit := 4*n + 20

	bit := make([]int, limit)
	freq := make([]int, limit)

	// Add val to BIT at idx
	add := func(idx, val int) {
		for ; idx < limit; idx += idx & -idx {
			bit[idx] += val
		}
	}

	// Query sum from 1 to idx
	query := func(idx int) int {
		res := 0
		for ; idx > 0; idx -= idx & -idx {
			res += bit[idx]
		}
		return res
	}

	curr := 0
	// Add initial prefix sum P[0] = 0
	startIdx := curr + offset
	add(startIdx, 1)
	freq[startIdx]++

	var ans int64 = 0

	for _, char := range s {
		if char == '0' {
			curr++
		} else {
			curr -= 3
		}

		// Count previous prefix sums satisfying P[l-1] <= curr - 2
		targetLe := curr - 2 + offset
		if targetLe > 0 {
			if targetLe >= limit {
				targetLe = limit - 1
			}
			ans += int64(query(targetLe))
		}

		// Count previous prefix sums satisfying P[l-1] == curr + 1
		targetEq := curr + 1 + offset
		if targetEq >= 0 && targetEq < limit {
			ans += int64(freq[targetEq])
		}

		// Add current prefix sum to data structures
		idx := curr + offset
		add(idx, 1)
		freq[idx]++
	}

	fmt.Fprintln(writer, ans)
}
```