← Home
For problem statement at 0-999/100-199/140-149/142/problemC.txt this is a correct solution, but verifier at 0-999/100-199/140-149/142/verifierC.go ends with test 1 failed: expected 1 got 2

exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

type Placement struct {
	col    int
	orient int
	top    int
}

type LocalRes struct {
	gain       int
	placements []Placement
}

type Parent struct {
	prev       uint32
	placements []Placement
}

func enumerate(col, a0, b0, h, w, fullMask int) map[uint32]LocalRes {
	res := make(map[uint32]LocalRes)
	cur := make([]Placement, 0, 8)

	var dfs func(a, b, c, count int)
	dfs = func(a, b, c, count int) {
		if a == fullMask {
			ns := uint32(b) | (uint32(c) << uint(h))
			if old, ok := res[ns]; !ok || count > old.gain {
				cp := make([]Placement, len(cur))
				copy(cp, cur)
				res[ns] = LocalRes{gain: count, placements: cp}
			}
			return
		}

		r := bits.TrailingZeros32(uint32((^a) & fullMask))

		dfs(a|(1<<r), b, c, count)

		if col+2 < w {
			if r+1 < h {
				pa := 1 << r
				pb := (1 << r) | (1 << (r + 1))
				pc := 1 << r
				if a&pa == 0 && b&pb == 0 && c&pc == 0 {
					cur = append(cur, Placement{col: col, orient: 0, top: r})
					dfs(a|pa, b|pb, c|pc, count+1)
					cur = cur[:len(cur)-1]
				}
			}
			if r-1 >= 0 {
				t := r - 1
				pa := 1 << r
				pb := (1 << t) | (1 << r)
				pc := 1 << r
				if a&pa == 0 && b&pb == 0 && c&pc == 0 {
					cur = append(cur, Placement{col: col, orient: 1, top: t})
					dfs(a|pa, b|pb, c|pc, count+1)
					cur = cur[:len(cur)-1]
				}
			}
		}

		if col+1 < w {
			if r+2 < h {
				t := r
				pa := (1 << t) | (1 << (t + 1)) | (1 << (t + 2))
				pb := 1 << (t + 1)
				if a&pa == 0 && b&pb == 0 {
					cur = append(cur, Placement{col: col, orient: 2, top: t})
					dfs(a|pa, b|pb, c, count+1)
					cur = cur[:len(cur)-1]
				}
			}
			if r-1 >= 0 && r+1 < h {
				t := r - 1
				pa := 1 << r
				pb := (1 << t) | (1 << (t + 1)) | (1 << (t + 2))
				if a&pa == 0 && b&pb == 0 {
					cur = append(cur, Placement{col: col, orient: 3, top: t})
					dfs(a|pa, b|pb, c, count+1)
					cur = cur[:len(cur)-1]
				}
			}
		}
	}

	dfs(a0, b0, 0, 0)
	return res
}

func cells(p Placement) [4][2]int {
	c := p.col
	t := p.top
	switch p.orient {
	case 0:
		return [4][2]int{{t, c}, {t, c + 1}, {t, c + 2}, {t + 1, c + 1}}
	case 1:
		return [4][2]int{{t + 1, c}, {t + 1, c + 1}, {t + 1, c + 2}, {t, c + 1}}
	case 2:
		return [4][2]int{{t, c}, {t + 1, c}, {t + 2, c}, {t + 1, c + 1}}
	default:
		return [4][2]int{{t, c + 1}, {t + 1, c + 1}, {t + 2, c + 1}, {t + 1, c}}
	}
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var n, m int
	fmt.Fscan(in, &n, &m)

	h, w := n, m
	transposed := false
	if h > w {
		h, w = w, h
		transposed = true
	}

	fullMask := (1 << h) - 1

	dp := map[uint32]int{0: 0}
	parents := make([]map[uint32]Parent, w+1)

	for col := 0; col < w; col++ {
		nextDP := make(map[uint32]int, len(dp)*2+1)
		nextParent := make(map[uint32]Parent, len(dp)*2+1)

		for state, val := range dp {
			a := int(state & uint32(fullMask))
			b := int(state >> uint(h))

			transitions := enumerate(col, a, b, h, w, fullMask)
			for ns, tr := range transitions {
				cand := val + tr.gain
				if cur, ok := nextDP[ns]; !ok || cand > cur {
					nextDP[ns] = cand
					nextParent[ns] = Parent{prev: state, placements: tr.placements}
				}
			}
		}

		dp = nextDP
		parents[col+1] = nextParent
	}

	ans := dp[0]

	allPlacements := make([]Placement, 0, ans)
	state := uint32(0)
	for col := w; col >= 1; col-- {
		p := parents[col][state]
		allPlacements = append(allPlacements, p.placements...)
		state = p.prev
	}

	board := make([][]byte, n)
	for i := 0; i < n; i++ {
		board[i] = make([]byte, m)
		for j := 0; j < m; j++ {
			board[i][j] = '.'
		}
	}

	for i, p := range allPlacements {
		ch := byte('A' + i)
		cs := cells(p)
		for _, cell := range cs {
			r, c := cell[0], cell[1]
			if !transposed {
				board[r][c] = ch
			} else {
				board[c][r] = ch
			}
		}
	}

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	fmt.Fprintln(out, ans)
	for i := 0; i < n; i++ {
		fmt.Fprintln(out, string(board[i]))
	}
}