For problem statement at 1000-1999/1900-1999/1940-1949/1942/problemF.txt this is a correct solution, but verifier at 1000-1999/1900-1999/1940-1949/1942/verifierF.go ends with test 1 failed
input:
2 2
0.556732 0.542621
2 2.527093
2 0.960721
expected:1
1
got:16569
15967
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"math"
"os"
)
func isqrt(n int64) int64 {
if n == 0 {
return 0
}
x := int64(math.Sqrt(float64(n)))
for (x+1)*(x+1) <= n {
x++
}
for x*x > n {
x--
}
return x
}
var a []int64
type Block struct {
L, R int
V0 int64
T int64
Diff bool
}
const CAP = 2000000000
func eval_forward(L, R int, X int64) int64 {
for i := L; i <= R; i++ {
X = isqrt(a[i] + X)
}
return X
}
func (b *Block) rebuild() {
v0 := eval_forward(b.L, b.R, 0)
v1 := eval_forward(b.L, b.R, CAP)
b.V0 = v0
if v1 == v0 {
b.Diff = false
b.T = 0
} else if v1 == v0+1 {
b.Diff = true
req := v1
for i := b.R; i >= b.L; i-- {
if req > CAP {
req = CAP
}
val := req*req - a[i]
if val < 0 {
req = 0
} else {
req = val
}
}
b.T = req
} else {
b.Diff = false
b.T = -1
}
}
func (b *Block) eval(X int64) int64 {
if b.T == -1 {
return eval_forward(b.L, b.R, X)
}
if b.Diff && X >= b.T {
return b.V0 + 1
}
return b.V0
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Buffer(make([]byte, 1024*1024*10), 1024*1024*10)
scanner.Split(bufio.ScanWords)
if !scanner.Scan() {
return
}
n := parseInt(scanner.Text())
scanner.Scan()
q := parseInt(scanner.Text())
a = make([]int64, n)
for i := 0; i < n; i++ {
scanner.Scan()
a[i] = parseIn64(scanner.Text())
}
B := 400
numBlocks := (n + B - 1) / B
blocks := make([]Block, numBlocks)
for i := 0; i < numBlocks; i++ {
L := i * B
R := L + B - 1
if R >= n {
R = n - 1
}
blocks[i] = Block{L: L, R: R}
blocks[i].rebuild()
}
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
for i := 0; i < q; i++ {
scanner.Scan()
k := parseInt(scanner.Text())
scanner.Scan()
x := parseIn64(scanner.Text())
idx := k - 1
a[idx] = x
b_idx := idx / B
blocks[b_idx].rebuild()
X := int64(0)
for j := 0; j < numBlocks; j++ {
X = blocks[j].eval(X)
}
fmt.Fprintln(out, X)
}
}
func parseInt(s string) int {
res := 0
for i := 0; i < len(s); i++ {
res = res*10 + int(s[i]-'0')
}
return res
}
func parseIn64(s string) int64 {
var res int64 = 0
for i := 0; i < len(s); i++ {
res = res*10 + int64(s[i]-'0')
}
return res
}