← Home
For problem statement at 1000-1999/1000-1099/1010-1019/1015/problemE2.txt this is a correct solution, but verifier at 1000-1999/1000-1099/1010-1019/1015/verifierE2.go ends with All 100 tests passed can you fix the verifier? package main

import (
	"bufio"
	"io"
	"os"
	"strconv"
)

type Star struct {
	x int16
	y int16
	s int16
}

func writeInt(w *bufio.Writer, x int) {
	var buf [20]byte
	b := strconv.AppendInt(buf[:0], int64(x), 10)
	w.Write(b)
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	p := 0

	nextInt := func() int {
		for p < len(data) && data[p] <= ' ' {
			p++
		}
		sign := 1
		if data[p] == '-' {
			sign = -1
			p++
		}
		v := 0
		for p < len(data) && data[p] > ' ' {
			v = v*10 + int(data[p]-'0')
			p++
		}
		return v * sign
	}

	nextToken := func() []byte {
		for p < len(data) && data[p] <= ' ' {
			p++
		}
		start := p
		for p < len(data) && data[p] > ' ' {
			p++
		}
		return data[start:p]
	}

	n := nextInt()
	m := nextInt()

	grid := make([]byte, n*m)
	for i := 0; i < n; i++ {
		s := nextToken()
		copy(grid[i*m:(i+1)*m], s)
	}

	minUL := make([]uint16, n*m)
	upCol := make([]uint16, m)

	for i := 0; i < n; i++ {
		var left uint16
		base := i * m
		for j := 0; j < m; j++ {
			if grid[base+j] == '*' {
				upCol[j]++
				left++
				if upCol[j] < left {
					minUL[base+j] = upCol[j]
				} else {
					minUL[base+j] = left
				}
			} else {
				upCol[j] = 0
				left = 0
			}
		}
	}

	rowDiff := make([]int16, n*(m+1))
	colDiff := make([]int16, (n+1)*m)
	downCol := make([]uint16, m)
	stars := make([]Star, 0)

	for i := n - 1; i >= 0; i-- {
		var right uint16
		base := i * m
		rowBase := i * (m + 1)
		for j := m - 1; j >= 0; j-- {
			if grid[base+j] == '*' {
				downCol[j]++
				right++
				minDR := downCol[j]
				if right < minDR {
					minDR = right
				}
				s := minUL[base+j]
				if minDR < s {
					s = minDR
				}
				if s > 1 {
					size := int(s - 1)
					stars = append(stars, Star{int16(i + 1), int16(j + 1), int16(size)})

					l := j - size
					r := j + size
					rowDiff[rowBase+l]++
					rowDiff[rowBase+r+1]--

					colDiff[(i-size)*m+j]++
					colDiff[(i+size+1)*m+j]--
				}
			} else {
				downCol[j] = 0
				right = 0
			}
		}
	}

	colAcc := make([]int, m)
	ok := true

	for i := 0; i < n && ok; i++ {
		rowBase := i * (m + 1)
		gridBase := i * m
		diffBase := i * m
		rowAcc := 0
		for j := 0; j < m; j++ {
			rowAcc += int(rowDiff[rowBase+j])
			colAcc[j] += int(colDiff[diffBase+j])
			covered := rowAcc > 0 || colAcc[j] > 0
			if covered != (grid[gridBase+j] == '*') {
				ok = false
				break
			}
		}
	}

	w := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer w.Flush()

	if !ok {
		w.WriteString("-1\n")
		return
	}

	writeInt(w, len(stars))
	w.WriteByte('\n')
	for _, st := range stars {
		writeInt(w, int(st.x))
		w.WriteByte(' ')
		writeInt(w, int(st.y))
		w.WriteByte(' ')
		writeInt(w, int(st.s))
		w.WriteByte('\n')
	}
}