← Home
For problem statement at 1000-1999/1100-1199/1190-1199/1198/problemA.txt this is a correct solution, but verifier at 1000-1999/1100-1199/1190-1199/1198/verifierA.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"sort"
)

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

	n := nextInt()
	I := nextInt()

	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = nextInt()
	}

	sort.Ints(a)

	freq := make([]int, 0, n)
	for i := 0; i < n; {
		j := i + 1
		for j < n && a[j] == a[i] {
			j++
		}
		freq = append(freq, j-i)
		i = j
	}

	m := len(freq)
	bits := int((8 * int64(I)) / int64(n))
	if bits > 20 {
		bits = 20
	}
	allowed := 1 << bits
	if allowed >= m {
		w := bufio.NewWriter(os.Stdout)
		fmt.Fprintln(w, 0)
		w.Flush()
		return
	}

	pref := make([]int, m+1)
	for i := 0; i < m; i++ {
		pref[i+1] = pref[i] + freq[i]
	}

	best := 0
	for i := 0; i+allowed <= m; i++ {
		cur := pref[i+allowed] - pref[i]
		if cur > best {
			best = cur
		}
	}

	ans := n - best
	w := bufio.NewWriter(os.Stdout)
	fmt.Fprintln(w, ans)
	w.Flush()
}