For problem statement at 0-999/600-699/610-619/611/problemE.txt this is a correct solution, but verifier at 0-999/600-699/610-619/611/verifierE.go ends with case 14 failed: expected 4 got 3
exit status 1 can you fix the verifier? package main
import (
"bufio"
"os"
"sort"
)
type FastScanner struct {
r *bufio.Reader
}
func NewFastScanner() *FastScanner {
return &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}
func (fs *FastScanner) NextInt() int {
sign, val := 1, 0
c, err := fs.r.ReadByte()
for (c < '0' || c > '9') && c != '-' {
c, err = fs.r.ReadByte()
if err != nil {
return 0
}
}
if c == '-' {
sign = -1
c, _ = fs.r.ReadByte()
}
for c >= '0' && c <= '9' {
val = val*10 + int(c-'0')
c, err = fs.r.ReadByte()
if err != nil {
break
}
}
return sign * val
}
type Fenwick struct {
n int
bit []int
}
func NewFenwick(n int) *Fenwick {
return &Fenwick{n: n, bit: make([]int, n+2)}
}
func (f *Fenwick) Add(idx, delta int) {
for i := idx + 1; i <= f.n; i += i & -i {
f.bit[i] += delta
}
}
func (f *Fenwick) Sum(idx int) int {
if idx < 0 {
return 0
}
res := 0
for i := idx + 1; i > 0; i -= i & -i {
res += f.bit[i]
}
return res
}
func (f *Fenwick) Total() int {
return f.Sum(f.n - 1)
}
// returns 0-based index of k-th (1-based k) element
func (f *Fenwick) Kth(k int) int {
pos := 0
bit := 1
for bit<<1 <= f.n {
bit <<= 1
}
for bit > 0 {
next := pos + bit
if next <= f.n && f.bit[next] < k {
k -= f.bit[next]
pos = next
}
bit >>= 1
}
return pos
}
type MultiSet struct {
vals []int
fw *Fenwick
}
func NewMultiSet(vals []int, cnt []int) *MultiSet {
fw := NewFenwick(len(vals))
for i, c := range cnt {
if c > 0 {
fw.Add(i, c)
}
}
return &MultiSet{vals: vals, fw: fw}
}
func (ms *MultiSet) total() int {
return ms.fw.Total()
}
func (ms *MultiSet) upperBound(x int) int {
return sort.SearchInts(ms.vals, x+1)
}
func (ms *MultiSet) removeMax() (int, bool) {
t := ms.fw.Total()
if t == 0 {
return 0, false
}
idx := ms.fw.Kth(t)
val := ms.vals[idx]
ms.fw.Add(idx, -1)
return val, true
}
func (ms *MultiSet) removeLE(cap int) bool {
pos := ms.upperBound(cap) - 1
if pos < 0 {
return false
}
le := ms.fw.Sum(pos)
if le <= 0 {
return false
}
idx := ms.fw.Kth(le)
ms.fw.Add(idx, -1)
return true
}
func (ms *MultiSet) removeInRange(lo, hi int) bool {
posHi := ms.upperBound(hi) - 1
if posHi < 0 {
return false
}
sumHi := ms.fw.Sum(posHi)
posLo := ms.upperBound(lo) - 1
sumLo := 0
if posLo >= 0 {
sumLo = ms.fw.Sum(posLo)
}
if sumHi-sumLo <= 0 {
return false
}
idx := ms.fw.Kth(sumHi)
ms.fw.Add(idx, -1)
return true
}
func main() {
in := NewFastScanner()
out := bufio.NewWriterSize(os.Stdout, 1<<20)
defer out.Flush()
n := in.NextInt()
a := in.NextInt()
b := in.NextInt()
c := in.NextInt()
str := []int{a, b, c}
sort.Ints(str)
a, b, c = str[0], str[1], str[2]
t := make([]int, n)
maxT := 0
for i := 0; i < n; i++ {
t[i] = in.NextInt()
if t[i] > maxT {
maxT = t[i]
}
}
if maxT > a+b+c {
out.WriteString("-1\n")
return
}
// compress values
sorted := make([]int, n)
copy(sorted, t)
sort.Ints(sorted)
uniq := make([]int, 0, n)
for i := 0; i < n; i++ {
if i == 0 || sorted[i] != sorted[i-1] {
uniq = append(uniq, sorted[i])
}
}
idxMap := make(map[int]int, len(uniq))
for i, v := range uniq {
idxMap[v] = i
}
cnt := make([]int, len(uniq))
for _, v := range t {
cnt[idxMap[v]]++
}
ms := NewMultiSet(uniq, cnt)
hours := 0
for ms.total() > 0 {
x, _ := ms.removeMax()
hours++
if x > b+c {
// all three needed, nothing else this hour
continue
} else if x > a+c {
// use b+c, try to use a on another
ms.removeLE(a)
} else if x > a+b {
// use a+c, try to use b on another
ms.removeLE(b)
} else {
if x > c {
// use a+b on x, c can take another
ms.removeLE(c)
} else {
// x <= c
usedB := false
if ms.removeInRange(a, b) {
usedB = true
}
aUsed := ms.removeLE(a)
if !usedB {
_ = ms.removeLE(a)
}
if !usedB && !aUsed {
_ = ms.removeLE(c)
}
}
}
}
out.WriteString(intToString(hours))
out.WriteByte('\n')
}
func intToString(x int) string {
if x == 0 {
return "0"
}
neg := false
if x < 0 {
neg = true
x = -x
}
buf := make([]byte, 0, 12)
for x > 0 {
buf = append(buf, byte('0'+x%10))
x /= 10
}
if neg {
buf = append(buf, '-')
}
// reverse
for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 {
buf[i], buf[j] = buf[j], buf[i]
}
return string(buf)
}