← Home
For problem statement at 2000-2999/2000-2099/2020-2029/2028/problemF.txt this is a correct solution, but verifier at 2000-2999/2000-2099/2020-2029/2028/verifierF.go ends with All 88 tests passed. can you fix the verifier? package main

import (
	"io"
	"os"
)

const (
	WMAX = 157
	KMAX = 20
)

func main() {
	data, _ := io.ReadAll(os.Stdin)
	idx := 0
	nData := len(data)
	nextInt := func() int {
		for idx < nData && (data[idx] < '0' || data[idx] > '9') {
			idx++
		}
		val := 0
		for idx < nData && data[idx] >= '0' && data[idx] <= '9' {
			val = val*10 + int(data[idx]-'0')
			idx++
		}
		return val
	}

	t := nextInt()
	out := make([]byte, 0, t*4)

	var dpArr1, dpArr2 [WMAX]uint64
	var prodArr1, prodArr2 [KMAX]int
	var bitsArr1, bitsArr2 [KMAX * WMAX]uint64

	for ; t > 0; t-- {
		n := nextInt()
		m := nextInt()

		W := (m >> 6) + 1
		var lastMask uint64
		if (m & 63) == 63 {
			lastMask = ^uint64(0)
		} else {
			lastMask = (uint64(1) << uint((m&63)+1)) - 1
		}
		infKey := m + 1

		dpPrev := dpArr1[:]
		dpCurr := dpArr2[:]
		for i := 0; i < W; i++ {
			dpPrev[i] = 0
			dpCurr[i] = 0
		}
		dpPrev[0] = 1
		dpPrevNonEmpty := true

		curProds := prodArr1[:]
		nxtProds := prodArr2[:]
		curBits := bitsArr1[:]
		nxtBits := bitsArr2[:]
		cnt := 0

		for i := 0; i < n; i++ {
			x := nextInt()
			for w := 0; w < W; w++ {
				dpCurr[w] = 0
			}
			newCnt := 0

			if dpPrevNonEmpty {
				np := x
				if x == 0 {
					np = 0
				} else if x > m {
					np = infKey
				}

				dstIdx := newCnt
				nxtProds[dstIdx] = np
				newCnt++
				dstOff := dstIdx * WMAX

				if np == infKey {
					for w := 0; w < W; w++ {
						nxtBits[dstOff+w] = dpPrev[w]
					}
				} else if np == 0 {
					for w := 0; w < W; w++ {
						v := dpPrev[w]
						nxtBits[dstOff+w] = v
						dpCurr[w] |= v
					}
				} else {
					ws := np >> 6
					bs := uint(np & 63)
					if bs == 0 {
						di := ws
						for w := 0; w < W; w++ {
							v := dpPrev[w]
							nxtBits[dstOff+w] = v
							if di < W {
								dpCurr[di] |= v
								di++
							}
						}
					} else {
						di := ws
						carry := uint64(0)
						inv := 64 - bs
						for w := 0; w < W; w++ {
							v := dpPrev[w]
							nxtBits[dstOff+w] = v
							if di < W {
								dpCurr[di] |= (v << bs) | carry
								carry = v >> inv
								di++
							}
						}
						if di < W {
							dpCurr[di] |= carry
						}
					}
				}
			}

			for g := 0; g < cnt; g++ {
				oldp := curProds[g]
				var np int
				if oldp == 0 || x == 0 {
					np = 0
				} else if oldp == infKey || x > m {
					np = infKey
				} else if x == 1 {
					np = oldp
				} else if oldp > m/x {
					np = infKey
				} else {
					np = oldp * x
				}

				dstIdx := -1
				for j := 0; j < newCnt; j++ {
					if nxtProds[j] == np {
						dstIdx = j
						break
					}
				}
				create := false
				if dstIdx < 0 {
					dstIdx = newCnt
					nxtProds[dstIdx] = np
					newCnt++
					create = true
				}

				srcOff := g * WMAX
				dstOff := dstIdx * WMAX

				if np == infKey {
					if create {
						for w := 0; w < W; w++ {
							nxtBits[dstOff+w] = curBits[srcOff+w]
						}
					} else {
						for w := 0; w < W; w++ {
							nxtBits[dstOff+w] |= curBits[srcOff+w]
						}
					}
				} else if np == 0 {
					if create {
						for w := 0; w < W; w++ {
							v := curBits[srcOff+w]
							nxtBits[dstOff+w] = v
							dpCurr[w] |= v
						}
					} else {
						for w := 0; w < W; w++ {
							v := curBits[srcOff+w]
							nxtBits[dstOff+w] |= v
							dpCurr[w] |= v
						}
					}
				} else {
					ws := np >> 6
					bs := uint(np & 63)
					if bs == 0 {
						di := ws
						if create {
							for w := 0; w < W; w++ {
								v := curBits[srcOff+w]
								nxtBits[dstOff+w] = v
								if di < W {
									dpCurr[di] |= v
									di++
								}
							}
						} else {
							for w := 0; w < W; w++ {
								v := curBits[srcOff+w]
								nxtBits[dstOff+w] |= v
								if di < W {
									dpCurr[di] |= v
									di++
								}
							}
						}
					} else {
						di := ws
						carry := uint64(0)
						inv := 64 - bs
						if create {
							for w := 0; w < W; w++ {
								v := curBits[srcOff+w]
								nxtBits[dstOff+w] = v
								if di < W {
									dpCurr[di] |= (v << bs) | carry
									carry = v >> inv
									di++
								}
							}
						} else {
							for w := 0; w < W; w++ {
								v := curBits[srcOff+w]
								nxtBits[dstOff+w] |= v
								if di < W {
									dpCurr[di] |= (v << bs) | carry
									carry = v >> inv
									di++
								}
							}
						}
						if di < W {
							dpCurr[di] |= carry
						}
					}
				}
			}

			dpCurr[W-1] &= lastMask
			dpCurrNonEmpty := false
			for w := 0; w < W; w++ {
				if dpCurr[w] != 0 {
					dpCurrNonEmpty = true
					break
				}
			}

			cnt = newCnt
			dpPrev, dpCurr = dpCurr, dpPrev
			dpPrevNonEmpty = dpCurrNonEmpty
			curProds, nxtProds = nxtProds, curProds
			curBits, nxtBits = nxtBits, curBits
		}

		if ((dpPrev[m>>6] >> uint(m&63)) & 1) != 0 {
			out = append(out, 'Y', 'E', 'S', '\n')
		} else {
			out = append(out, 'N', 'O', '\n')
		}
	}

	os.Stdout.Write(out)
}