For problem statement at 0-999/600-699/690-699/695/problemC.txt this is a correct solution, but verifier at 0-999/600-699/690-699/695/verifierC.go ends with case 13 failed: expected 3 got 2
input:
1 3
0 9
10 3
3 2
3 2
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"math/bits"
"os"
"sort"
)
type Dir struct {
x, y int64
}
type Item struct {
t int64
id int
}
type SmallSet struct {
len uint8
ids [7]uint16
}
type SetKey struct {
len uint8
ids [7]uint16
}
var k, n int
var blockers [][]SmallSet
var blockerCnt [][]uint8
var useMaskByRem [][]int
var pc []int
var memo []map[SetKey]uint8
func abs64(a int64) int64 {
if a < 0 {
return -a
}
return a
}
func gcd(a, b int64) int64 {
for b != 0 {
a, b = b, a%b
}
if a < 0 {
return -a
}
return a
}
func buildNext(cur SetKey, remIdx int, block SmallSet, limit int) (SetKey, bool) {
var base [7]uint16
q := 0
for i := 0; i < int(cur.len); i++ {
if i != remIdx {
base[q] = cur.ids[i]
q++
}
}
var nk SetKey
i, j, p := 0, 0, 0
blen := int(block.len)
for i < q || j < blen {
var v uint16
if j == blen || (i < q && base[i] < block.ids[j]) {
v = base[i]
i++
} else if i == q || block.ids[j] < base[i] {
v = block.ids[j]
j++
} else {
v = base[i]
i++
j++
}
if p == 0 || nk.ids[p-1] != v {
if p == limit {
return nk, false
}
nk.ids[p] = v
p++
}
}
nk.len = uint8(p)
return nk, true
}
func solve(mask int, cur SetKey) bool {
if cur.len == 0 {
return true
}
rem := pc[mask]
if int(cur.len) > rem {
return false
}
if memo[mask] == nil {
memo[mask] = make(map[SetKey]uint8)
} else {
if v := memo[mask][cur]; v != 0 {
return v == 2
}
}
for i := 0; i < int(cur.len); i++ {
x := int(cur.ids[i])
if useMaskByRem[rem][x]&mask == 0 {
memo[mask][cur] = 1
return false
}
}
limit := rem - 1
for i := 0; i < int(cur.len); i++ {
x := int(cur.ids[i])
bm := useMaskByRem[rem][x] & mask
for bm > 0 {
bit := bm & -bm
j := bits.TrailingZeros(uint(bit))
nk, ok := buildNext(cur, i, blockers[j][x], limit)
if ok && solve(mask^bit, nk) {
memo[mask][cur] = 2
return true
}
bm ^= bit
}
}
memo[mask][cur] = 1
return false
}
func main() {
in := bufio.NewReaderSize(os.Stdin, 1<<20)
fmt.Fscan(in, &k, &n)
ax := make([]int64, k)
ay := make([]int64, k)
for i := 0; i < k; i++ {
fmt.Fscan(in, &ax[i], &ay[i])
}
mx := make([]int64, n)
my := make([]int64, n)
for i := 0; i < n; i++ {
fmt.Fscan(in, &mx[i], &my[i])
}
blockers = make([][]SmallSet, k)
blockerCnt = make([][]uint8, k)
for j := 0; j < k; j++ {
blockers[j] = make([]SmallSet, n)
blockerCnt[j] = make([]uint8, n)
}
for j := 0; j < k; j++ {
groups := make(map[Dir][]Item, n)
for i := 0; i < n; i++ {
dx := mx[i] - ax[j]
dy := my[i] - ay[j]
g := gcd(abs64(dx), abs64(dy))
dir := Dir{dx / g, dy / g}
groups[dir] = append(groups[dir], Item{g, i})
}
for _, arr := range groups {
sort.Slice(arr, func(a, b int) bool {
return arr[a].t < arr[b].t
})
prefix := make([]int, 0, len(arr))
for pos, it := range arr {
if pos < k {
blockerCnt[j][it.id] = uint8(pos)
var s SmallSet
s.len = uint8(pos)
if pos > 0 {
tmp := make([]uint16, pos)
for z := 0; z < pos; z++ {
tmp[z] = uint16(prefix[z])
}
sort.Slice(tmp, func(a, b int) bool {
return tmp[a] < tmp[b]
})
for z := 0; z < pos; z++ {
s.ids[z] = tmp[z]
}
}
blockers[j][it.id] = s
} else {
blockerCnt[j][it.id] = uint8(k)
}
prefix = append(prefix, it.id)
}
}
}
useMaskByRem = make([][]int, k+1)
for r := 0; r <= k; r++ {
useMaskByRem[r] = make([]int, n)
}
for x := 0; x < n; x++ {
for r := 1; r <= k; r++ {
m := 0
for j := 0; j < k; j++ {
if int(blockerCnt[j][x]) < r {
m |= 1 << j
}
}
useMaskByRem[r][x] = m
}
}
pc = make([]int, 1<<k)
for mask := 0; mask < (1 << k); mask++ {
pc[mask] = bits.OnesCount(uint(mask))
}
memo = make([]map[SetKey]uint8, 1<<k)
allMask := (1 << k) - 1
ans := 0
for i := 0; i < n; i++ {
var s SetKey
s.len = 1
s.ids[0] = uint16(i)
if solve(allMask, s) {
ans++
}
}
fmt.Println(ans)
}