For problem statement at 1000-1999/1400-1499/1450-1459/1452/problemF.txt this is a correct solution, but verifier at 1000-1999/1400-1499/1450-1459/1452/verifierF.go ends with test 7 failed at result 1: expected -1 got 2
exit status 1 can you fix the verifier? package main
import (
"io"
"os"
"strconv"
)
const INF int64 = 1 << 60
var (
n int
cnt []int64
pow2 []int64
totalUnits int64
totalCountAll int64
)
func evalA(y int, s int64) int64 {
if s <= 0 {
return 0
}
ops := int64(0)
need := s
for j := y; j < n; j++ {
c := cnt[j]
if need <= c {
return ops
}
if j == n-1 {
return INF
}
need -= c
take := (need + 1) >> 1
ops += take
need = take
}
return INF
}
func minB(y int, l, r int64) int64 {
if l > r {
return INF
}
ans := INF
offset := int64(0)
for {
c := cnt[y]
freeR := r
if freeR > c {
freeR = c
}
if l <= freeR {
v := offset - freeR
if v < ans {
ans = v
}
}
if y == n-1 || r <= c {
return ans
}
if r > c && ((r-c)&1) == 1 {
t := (r - c + 1) >> 1
a := evalA(y+1, t)
if a < INF {
v := offset - c + 1 + (a - t)
if v < ans {
ans = v
}
}
}
if l < c+1 {
l = c + 1
}
l = (l - c + 1) >> 1
if l < 1 {
l = 1
}
r = (r - c) >> 1
offset -= c
y++
if l > r || y >= n {
return ans
}
}
}
func solve(x int, k int64) int64 {
if k > totalUnits {
return -1
}
if x == n-1 {
if k <= totalCountAll {
return 0
}
return k - totalCountAll
}
var g, lowCap int64
for i := 0; i <= x; i++ {
g += cnt[i]
lowCap += cnt[i] * pow2[i]
}
if k <= g {
return 0
}
d := k - g
l := lowCap - g
y := x + 1
u := pow2[y]
lb := int64(0)
if d > l {
lb = (d - l + u - 1) / u
}
ans := INF
upper := (d - 1) >> 1
if lb <= upper {
v := minB(y, lb, upper)
if v < INF {
cost := d + v
if cost < ans {
ans = cost
}
}
}
s0 := lb
half := (d + 1) >> 1
if s0 < half {
s0 = half
}
a := evalA(y, s0)
if a < INF {
cost := a + s0
if cost < ans {
ans = cost
}
}
if ans >= INF {
return -1
}
return ans
}
func main() {
data, _ := io.ReadAll(os.Stdin)
idx := 0
nextInt := func() int64 {
for idx < len(data) {
b := data[idx]
if b > ' ' {
break
}
idx++
}
var v int64
for idx < len(data) {
b := data[idx]
if b < '0' || b > '9' {
break
}
v = v*10 + int64(b-'0')
idx++
}
return v
}
n = int(nextInt())
q := int(nextInt())
cnt = make([]int64, n)
pow2 = make([]int64, n+1)
pow2[0] = 1
for i := 1; i <= n; i++ {
pow2[i] = pow2[i-1] << 1
}
for i := 0; i < n; i++ {
cnt[i] = nextInt()
totalCountAll += cnt[i]
totalUnits += cnt[i] * pow2[i]
}
out := make([]byte, 0, q*4)
for ; q > 0; q-- {
t := nextInt()
if t == 1 {
pos := int(nextInt())
val := nextInt()
delta := val - cnt[pos]
cnt[pos] = val
totalCountAll += delta
totalUnits += delta * pow2[pos]
} else {
x := int(nextInt())
k := nextInt()
ans := solve(x, k)
out = strconv.AppendInt(out, ans, 10)
out = append(out, '\n')
}
}
os.Stdout.Write(out)
}