← 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 case 2 failed: N=37 K=73 expected:
Yes
28
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

got:
Yes
28
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 28 27 26 25 24 23 22 21 20 19

exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"os"
	"strconv"
	"strings"
)

type Pair struct {
	num int
	w   int
}

func subset(items []Pair, target int) ([]int, bool) {
	prev := make([]int, target+1)
	choice := make([]int, target+1)
	for i := 1; i <= target; i++ {
		prev[i] = -1
	}
	prev[0] = -2
	for idx, it := range items {
		w := it.w
		if w > target {
			continue
		}
		for s := target; s >= w; s-- {
			if prev[s] == -1 && prev[s-w] != -1 {
				prev[s] = s - w
				choice[s] = idx
			}
		}
	}
	if prev[target] == -1 {
		return nil, false
	}
	res := make([]int, 0)
	for cur := target; cur > 0; cur = prev[cur] {
		res = append(res, items[choice[cur]].num)
	}
	return res, true
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	var n int
	var k int64
	for {
		var b byte
		var err error
		for {
			b, err = in.ReadByte()
			if err != nil {
				return
			}
			if b > ' ' {
				break
			}
		}
		sign := 1
		if b == '-' {
			sign = -1
			b, _ = in.ReadByte()
		}
		x := 0
		for b > ' ' {
			x = x*10 + int(b-'0')
			b, err = in.ReadByte()
			if err != nil {
				break
			}
		}
		n = sign * x
		break
	}
	for {
		var b byte
		var err error
		for {
			b, err = in.ReadByte()
			if err != nil {
				return
			}
			if b > ' ' {
				break
			}
		}
		sign := int64(1)
		if b == '-' {
			sign = -1
			b, _ = in.ReadByte()
		}
		var x int64
		for b > ' ' {
			x = x*10 + int64(b-'0')
			b, err = in.ReadByte()
			if err != nil {
				break
			}
		}
		k = sign * x
		break
	}

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

	pref := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		pref[i] = pref[i-1] + int64(d[i]-1)
	}

	if k > pref[n] {
		out := bufio.NewWriterSize(os.Stdout, 1<<20)
		out.WriteString("No\n")
		out.Flush()
		return
	}

	m := n
	for m > 1 && k <= pref[m/2] {
		m /= 2
	}
	h := m / 2
	target := int(k - pref[h])

	maxW := 0
	ones := 0
	for i := h + 1; i <= m; i++ {
		w := d[i] - 1
		if w > maxW {
			maxW = w
		}
		if w == 1 {
			ones++
		}
	}

	var selected []int
	ok := false

	if ones >= maxW-1 {
		buckets := make([][]int, maxW+1)
		for i := h + 1; i <= m; i++ {
			w := d[i] - 1
			buckets[w] = append(buckets[w], i)
		}
		rem := target
		selected = make([]int, 0)
		for w := maxW; w >= 2; w-- {
			if rem == 0 {
				break
			}
			take := rem / w
			if take > len(buckets[w]) {
				take = len(buckets[w])
			}
			if take > 0 {
				selected = append(selected, buckets[w][:take]...)
				rem -= take * w
			}
		}
		if rem <= len(buckets[1]) {
			selected = append(selected, buckets[1][:rem]...)
			ok = true
		}
	}

	if !ok {
		items := make([]Pair, 0, m-h)
		for i := h + 1; i <= m; i++ {
			items = append(items, Pair{i, d[i] - 1})
		}
		selected, ok = subset(items, target)
		if !ok {
			out := bufio.NewWriterSize(os.Stdout, 1<<20)
			out.WriteString("No\n")
			out.Flush()
			return
		}
	}

	ans := make([]int, h+len(selected))
	for i := 0; i < h; i++ {
		ans[i] = i + 1
	}
	copy(ans[h:], selected)

	var sb strings.Builder
	sb.Grow(8 + len(ans)*8)
	sb.WriteString("Yes\n")
	sb.WriteString(strconv.Itoa(len(ans)))
	sb.WriteByte('\n')
	for i, v := range ans {
		if i > 0 {
			sb.WriteByte(' ')
		}
		sb.WriteString(strconv.Itoa(v))
	}
	sb.WriteByte('\n')

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	out.WriteString(sb.String())
	out.Flush()
}