For problem statement at 0-999/200-299/230-239/232/problemE.txt this is a correct solution, but verifier at 0-999/200-299/230-239/232/verifierE.go ends with test 3 failed
expected:
No
No
No
Yes
No
got:
No
Yes
No
Yes
Yes
exit status 1 can you fix the verifier? ```go
package main
import (
"bufio"
"io"
"os"
)
type Query struct {
r1, c1, r2, c2 int
}
var (
buffer []byte
cursor int
queries []Query
answers []bool
grid []string
mask1 [505][505][8]uint64
mask2 [505][505][8]uint64
)
func nextInt() int {
for cursor < len(buffer) && (buffer[cursor] < '0' || buffer[cursor] > '9') {
cursor++
}
if cursor >= len(buffer) {
return 0
}
res := 0
for cursor < len(buffer) && buffer[cursor] >= '0' && buffer[cursor] <= '9' {
res = res*10 + int(buffer[cursor]-'0')
cursor++
}
return res
}
func nextString() string {
for cursor < len(buffer) && buffer[cursor] <= ' ' {
cursor++
}
if cursor >= len(buffer) {
return ""
}
start := cursor
for cursor < len(buffer) && buffer[cursor] > ' ' {
cursor++
}
return string(buffer[start:cursor])
}
func solve(r1, r2, c1, c2 int, qIdx []int) {
if len(qIdx) == 0 {
return
}
if r1 == r2 && c1 == c2 {
for _, id := range qIdx {
answers[id] = true
}
return
}
if r2-r1 > c2-c1 {
mid := (r1 + r2) / 2
var qCross, qTop, qBot []int
for _, id := range qIdx {
q := queries[id]
if q.r1 <= mid && q.r2 >= mid {
qCross = append(qCross, id)
} else if q.r2 < mid {
qTop = append(qTop, id)
} else {
qBot = append(qBot, id)
}
}
if len(qCross) > 0 {
numWords := (c2 - c1 + 1 + 63) / 64
for r := mid; r >= r1; r-- {
for c := c2; c >= c1; c-- {
for w := 0; w < numWords; w++ {
mask1[r][c][w] = 0
}
if grid[r][c] == '#' {
continue
}
if r == mid {
bitIdx := c - c1
mask1[r][c][bitIdx/64] |= 1 << (bitIdx % 64)
}
if r < mid && grid[r+1][c] == '.' {
for w := 0; w < numWords; w++ {
mask1[r][c][w] |= mask1[r+1][c][w]
}
}
if c < c2 && grid[r][c+1] == '.' {
for w := 0; w < numWords; w++ {
mask1[r][c][w] |= mask1[r][c+1][w]
}
}
}
}
for r := mid; r <= r2; r++ {
for c := c1; c <= c2; c++ {
for w := 0; w < numWords; w++ {
mask2[r][c][w] = 0
}
if grid[r][c] == '#' {
continue
}
if r == mid {
bitIdx := c - c1
mask2[r][c][bitIdx/64] |= 1 << (bitIdx % 64)
}
if r > mid && grid[r-1][c] == '.' {
for w := 0; w < numWords; w++ {
mask2[r][c][w] |= mask2[r-1][c][w]
}
}
if c > c1 && grid[r][c-1] == '.' {
for w := 0; w < numWords; w++ {
mask2[r][c][w] |= mask2[r][c-1][w]
}
}
}
}
for _, id := range qCross {
q := queries[id]
ans := false
for w := 0; w < numWords; w++ {
if (mask1[q.r1][q.c1][w] & mask2[q.r2][q.c2][w]) != 0 {
ans = true
break
}
}
answers[id] = ans
}
}
solve(r1, mid-1, c1, c2, qTop)
solve(mid+1, r2, c1, c2, qBot)
} else {
mid := (c1 + c2) / 2
var qCross, qLeft, qRight []int
for _, id := range qIdx {
q := queries[id]
if q.c1 <= mid && q.c2 >= mid {
qCross = append(qCross, id)
} else if q.c2 < mid {
qLeft = append(qLeft, id)
} else {
qRight = append(qRight, id)
}
}
if len(qCross) > 0 {
numWords := (r2 - r1 + 1 + 63) / 64
for c := mid; c >= c1; c-- {
for r := r2; r >= r1; r-- {
for w := 0; w < numWords; w++ {
mask1[r][c][w] = 0
}
if grid[r][c] == '#' {
continue
}
if c == mid {
bitIdx := r - r1
mask1[r][c][bitIdx/64] |= 1 << (bitIdx % 64)
}
if c < mid && grid[r][c+1] == '.' {
for w := 0; w < numWords; w++ {
mask1[r][c][w] |= mask1[r][c+1][w]
}
}
if r < r2 && grid[r+1][c] == '.' {
for w := 0; w < numWords; w++ {
mask1[r][c][w] |= mask1[r+1][c][w]
}
}
}
}
for c := mid; c <= c2; c++ {
for r := r1; r <= r2; r++ {
for w := 0; w < numWords; w++ {
mask2[r][c][w] = 0
}
if grid[r][c] == '#' {
continue
}
if c == mid {
bitIdx := r - r1
mask2[r][c][bitIdx/64] |= 1 << (bitIdx % 64)
}
if c > mid && grid[r][c-1] == '.' {
for w := 0; w < numWords; w++ {
mask2[r][c][w] |= mask2[r][c-1][w]
}
}
if r > r1 && grid[r-1][c] == '.' {
for w := 0; w < numWords; w++ {
mask2[r][c][w] |= mask2[r-1][c][w]
}
}
}
}
for _, id := range qCross {
q := queries[id]
ans := false
for w := 0; w < numWords; w++ {
if (mask1[q.r1][q.c1][w] & mask2[q.r2][q.c2][w]) != 0 {
ans = true
break
}
}
answers[id] = ans
}
}
solve(r1, r2, c1, mid-1, qLeft)
solve(r1, r2, mid+1, c2, qRight)
}
}
func main() {
buffer, _ = io.ReadAll(os.Stdin)
n := nextInt()
m := nextInt()
if n == 0 || m == 0 {
return
}
grid = make([]string, n+1)
for i := 1; i <= n; i++ {
grid[i] = " " + nextString()
}
q := nextInt()
queries = make([]Query, q)
answers = make([]bool, q)
qIdx := make([]int, q)
for i := 0; i < q; i++ {
queries[i].r1 = nextInt()
queries[i].c1 = nextInt()
queries[i].r2 = nextInt()
queries[i].c2 = nextInt()
qIdx[i] = i
}
solve(1, n, 1, m, qIdx)
out := bufio.NewWriter(os.Stdout)
for i := 0; i < q; i++ {
if answers[i] {
out.WriteString("Yes\n")
} else {
out.WriteString("No\n")
}
}
out.Flush()
}
```