← Home
For problem statement at 0-999/300-399/360-369/367/problemD.txt this is a correct solution, but verifier at 0-999/300-399/360-369/367/verifierD.go ends with All tests passed can you fix the verifier? package main

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

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var n, m, d int
	fmt.Fscan(in, &n, &m, &d)
	setid := make([]int, n+1)
	minA := make([]int, m)
	maxA := make([]int, m)
	for i := 0; i < m; i++ {
		var si int
		fmt.Fscan(in, &si)
		minA[i] = n + 1
		maxA[i] = 0
		for j := 0; j < si; j++ {
			var v int
			fmt.Fscan(in, &v)
			setid[v] = i
			minA[i] = min(minA[i], v)
			maxA[i] = max(maxA[i], v)
		}
	}
	type Block struct {
		l, r, sid int
	}
	var blocks []Block
	if n > 0 {
		start := 1
		curr_sid := setid[1]
		for i := 2; i <= n; i++ {
			if setid[i] == curr_sid {
				continue
			}
			blocks = append(blocks, Block{start, i - 1, curr_sid})
			start = i
			curr_sid = setid[i]
		}
		blocks = append(blocks, Block{start, n, curr_sid})
	}
	B := len(blocks)
	L := n - d + 1
	ans := m + 1
	for mask := 1; mask < (1 << m); mask++ {
		minu := n + 1
		maxu := 0
		for i := 0; i < m; i++ {
			if (mask & (1 << i)) != 0 {
				minu = min(minu, minA[i])
				maxu = max(maxu, maxA[i])
			}
		}
		if minu > d {
			continue
		}
		if maxu < L {
			continue
		}
		current := 0
		started := false
		good := true
		for b := 0; b < B; b++ {
			sid := blocks[b].sid
			is_sel := (mask & (1 << sid)) != 0
			if is_sel {
				if current >= d && started {
					good = false
					break
				}
				current = 0
				started = true
			} else {
				current += (blocks[b].r - blocks[b].l + 1)
			}
		}
		if good {
			k := bits.OnesCount(uint(mask))
			ans = min(ans, k)
		}
	}
	fmt.Println(ans)
}