For problem statement at 0-999/400-499/470-479/475/problemC.txt this is a correct solution, but verifier at 0-999/400-499/470-479/475/verifierC.go ends with case 71 mismatch
expected:4
got:-1
input:
2 4
XX..
X...
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
"sort"
)
func main() {
reader := bufio.NewReader(os.Stdin)
var n, m int
if _, err := fmt.Fscan(reader, &n, &m); err != nil {
return
}
grid := make([]string, n)
for i := 0; i < n; i++ {
fmt.Fscan(reader, &grid[i])
}
rMin, rMax := n, -1
cMin, cMax := m, -1
C := 0
prefix := make([][]int, n+1)
for i := range prefix {
prefix[i] = make([]int, m+1)
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
val := 0
if grid[i][j] == 'X' {
val = 1
C++
if i < rMin {
rMin = i
}
if i > rMax {
rMax = i
}
if j < cMin {
cMin = j
}
if j > cMax {
cMax = j
}
}
prefix[i+1][j+1] = prefix[i][j+1] + prefix[i+1][j] - prefix[i][j] + val
}
}
if C == 0 {
fmt.Println(-1)
return
}
H := rMax - rMin + 1
W := cMax - cMin + 1
K := H*W - C
if K < 0 {
fmt.Println(-1)
return
}
if K == 0 {
if H < W {
fmt.Println(H)
} else {
fmt.Println(W)
}
return
}
type Candidate struct {
x, y, area int
}
var candidates []Candidate
for i := 1; i*i <= K; i++ {
if K%i == 0 {
d1 := i
d2 := K / i
x1 := H - d1
y1 := W - d2
if x1 >= 1 && y1 >= 1 {
candidates = append(candidates, Candidate{x1, y1, x1 * y1})
}
x2 := H - d2
y2 := W - d1
if x2 >= 1 && y2 >= 1 {
if x1 != x2 || y1 != y2 {
candidates = append(candidates, Candidate{x2, y2, x2 * y2})
}
}
}
}
sort.Slice(candidates, func(i, j int) bool {
return candidates[i].area < candidates[j].area
})
getSum := func(r1, c1, r2, c2 int) int {
return prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]
}
for _, cand := range candidates {
x := cand.x
y := cand.y
rows := rMax - x + 1 - rMin + 1
cols := cMax - y + 1 - cMin + 1
if rows <= 0 || cols <= 0 {
continue
}
dp := make([]bool, cols)
possible := false
for i := 0; i < rows; i++ {
r := rMin + i
anyTrue := false
for j := 0; j < cols; j++ {
c := cMin + j
valid := getSum(r, c, r+x-1, c+y-1) == x*y
if i == 0 && j == 0 {
dp[j] = valid
} else {
if valid {
fromTop := false
if i > 0 && dp[j] {
fromTop = true
}
fromLeft := false
if j > 0 && dp[j-1] {
fromLeft = true
}
dp[j] = fromTop || fromLeft
} else {
dp[j] = false
}
}
if dp[j] {
anyTrue = true
}
}
if !anyTrue {
break
}
if i == rows-1 {
possible = dp[cols-1]
}
}
if possible {
fmt.Println(cand.area)
return
}
}
fmt.Println(-1)
}