← Home
For problem statement at 1000-1999/1800-1899/1850-1859/1852/problemC.txt this is a correct solution, but verifier at 1000-1999/1800-1899/1850-1859/1852/verifierC.go ends with All tests passed can you fix the verifier? package main

import (
	"bytes"
	"io"
	"os"
	"strconv"
)

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt64() int64 {
	for fs.idx < fs.n && fs.data[fs.idx] <= ' ' {
		fs.idx++
	}
	var v int64
	for fs.idx < fs.n && fs.data[fs.idx] > ' ' {
		v = v*10 + int64(fs.data[fs.idx]-'0')
		fs.idx++
	}
	return v
}

type MaxHeap struct {
	a []int64
}

func (h *MaxHeap) Len() int {
	return len(h.a)
}

func (h *MaxHeap) Top() int64 {
	return h.a[0]
}

func (h *MaxHeap) Push(x int64) {
	h.a = append(h.a, x)
	i := len(h.a) - 1
	for i > 0 {
		p := (i - 1) >> 1
		if h.a[p] >= h.a[i] {
			break
		}
		h.a[p], h.a[i] = h.a[i], h.a[p]
		i = p
	}
}

func (h *MaxHeap) Pop() int64 {
	n := len(h.a)
	res := h.a[0]
	last := h.a[n-1]
	h.a = h.a[:n-1]
	if n == 1 {
		return res
	}
	h.a[0] = last
	i := 0
	for {
		l := i*2 + 1
		if l >= len(h.a) {
			break
		}
		r := l + 1
		mx := l
		if r < len(h.a) && h.a[r] > h.a[l] {
			mx = r
		}
		if h.a[i] >= h.a[mx] {
			break
		}
		h.a[i], h.a[mx] = h.a[mx], h.a[i]
		i = mx
	}
	return res
}

func main() {
	fs := NewFastScanner()
	t := int(fs.NextInt64())
	var out bytes.Buffer

	for ; t > 0; t-- {
		n := int(fs.NextInt64())
		k := fs.NextInt64()

		h := MaxHeap{}
		var prev int64
		var ans int64

		for i := 0; i < n; i++ {
			a := fs.NextInt64()
			cur := a % k
			if i == 0 {
				prev = cur
				ans = cur
				continue
			}
			delta := cur - prev
			if delta < 0 {
				h.Push(-delta)
			} else if delta > 0 {
				threshold := k - delta
				if h.Len() > 0 && h.Top() > threshold {
					x := h.Pop()
					h.Push(threshold)
					ans += k - x
				} else {
					ans += delta
				}
			}
			prev = cur
		}

		out.WriteString(strconv.FormatInt(ans, 10))
		out.WriteByte('\n')
	}

	os.Stdout.Write(out.Bytes())
}