← Home
For problem statement at 0-999/900-999/920-929/922/problemF.txt this is a correct solution, but verifier at 0-999/900-999/920-929/922/verifierF.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
)

const SMALL = 5000

func exactChoose(divCnt []int, l, r, target int) ([]int, bool) {
	if target < 0 {
		return nil, false
	}
	nums := make([]int, 0, r-l+1)
	ws := make([]int, 0, r-l+1)
	total := 0
	for v := l; v <= r; v++ {
		w := divCnt[v] - 1
		nums = append(nums, v)
		ws = append(ws, w)
		total += w
	}
	if target > total {
		return nil, false
	}
	comp := false
	if target > total-target {
		target = total - target
		comp = true
	}
	dp := make([]bool, target+1)
	prevSum := make([]int, target+1)
	prevIdx := make([]int, target+1)
	for i := 1; i <= target; i++ {
		prevIdx[i] = -1
	}
	dp[0] = true
	for i, w := range ws {
		if w > target {
			continue
		}
		for s := target; s >= w; s-- {
			if !dp[s] && dp[s-w] {
				dp[s] = true
				prevSum[s] = s - w
				prevIdx[s] = i
			}
		}
	}
	if !dp[target] {
		return nil, false
	}
	chosen := make([]bool, len(ws))
	for s := target; s > 0; s = prevSum[s] {
		i := prevIdx[s]
		if i < 0 {
			return nil, false
		}
		chosen[i] = true
	}
	res := make([]int, 0)
	if !comp {
		for i, ok := range chosen {
			if ok {
				res = append(res, nums[i])
			}
		}
	} else {
		for i, ok := range chosen {
			if !ok {
				res = append(res, nums[i])
			}
		}
	}
	return res, true
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	var n, k int
	fmt.Fscan(in, &n, &k)

	divCnt := make([]int, n+1)
	for i := 1; i <= n; i++ {
		for j := i; j <= n; j += i {
			divCnt[j]++
		}
	}

	F := make([]int, n+1)
	for i := 1; i <= n; i++ {
		F[i] = F[i-1] + divCnt[i] - 1
	}

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

	if k > F[n] {
		fmt.Fprintln(out, "No")
		return
	}

	cur := n
	for cur > 1 && k <= F[cur/2] {
		cur /= 2
	}

	m := cur / 2
	r := k - F[m]

	var U []int
	var ok bool

	if cur <= SMALL {
		U, ok = exactChoose(divCnt, m+1, cur, r)
	} else {
		buckets := make([][]int, 2048)
		maxW := 0
		c1 := 0
		for v := m + 1; v <= cur; v++ {
			w := divCnt[v] - 1
			if w >= len(buckets) {
				nb := make([][]int, w*2+1)
				copy(nb, buckets)
				buckets = nb
			}
			buckets[w] = append(buckets[w], v)
			if w > maxW {
				maxW = w
			}
			if w == 1 {
				c1++
			}
		}
		if c1 < maxW {
			U, ok = exactChoose(divCnt, m+1, cur, r)
		} else {
			prefix := make([]int, maxW+1)
			for w := 1; w <= maxW; w++ {
				prefix[w] = prefix[w-1] + w*len(buckets[w])
			}
			rem := r
			U = make([]int, 0)
			ok = true
			for w := maxW; w >= 1; w-- {
				c := len(buckets[w])
				if c == 0 {
					continue
				}
				sp := prefix[w-1]
				x := 0
				if rem > sp {
					x = (rem - sp + w - 1) / w
				}
				if x > c {
					ok = false
					break
				}
				if x > 0 {
					U = append(U, buckets[w][:x]...)
					rem -= x * w
				}
			}
			if rem != 0 {
				ok = false
			}
		}
	}

	if !ok {
		fmt.Fprintln(out, "No")
		return
	}

	ans := make([]int, 0, m+len(U))
	for i := 1; i <= m; i++ {
		ans = append(ans, i)
	}
	ans = append(ans, U...)

	fmt.Fprintln(out, "Yes")
	fmt.Fprintln(out, len(ans))
	for i, v := range ans {
		if i > 0 {
			fmt.Fprint(out, " ")
		}
		fmt.Fprint(out, v)
	}
	fmt.Fprintln(out)
}