← Home
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)
}