← Home
For problem statement at 0-999/900-999/950-959/958/problemE2.txt this is a correct solution, but verifier at 0-999/900-999/950-959/958/verifierE2.go ends with reference runtime error on test 1: exec: "ref958E2.bin": executable file not found in $PATH
Input used:
2 4
1 4 6 7


exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"sort"
)

type Item struct {
	v int64
	i int
}

type PQ []Item

func (pq PQ) Len() int           { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].v < pq[j].v }
func (pq PQ) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x interface{}) {
	*pq = append(*pq, x.(Item))
}
func (pq *PQ) Pop() interface{} {
	old := *pq
	n := len(old)
	x := old[n-1]
	*pq = old[0 : n-1]
	return x
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1024*1024), 10*1024*1024)

	scanInt := func() int {
		scanner.Scan()
		res := 0
		for _, b := range scanner.Bytes() {
			res = res*10 + int(b-'0')
		}
		return res
	}

	scanInt64 := func() int64 {
		scanner.Scan()
		var res int64
		for _, b := range scanner.Bytes() {
			res = res*10 + int64(b-'0')
		}
		return res
	}

	if !scanner.Scan() {
		return
	}
	resK := 0
	for _, b := range scanner.Bytes() {
		resK = resK*10 + int(b-'0')
	}
	K := resK
	N := scanInt()

	T := make([]int64, N)
	for i := 0; i < N; i++ {
		T[i] = scanInt64()
	}

	sort.Slice(T, func(i, j int) bool { return T[i] < T[j] })

	V := make([]int64, N+1)
	L := make([]int, N+1)
	R := make([]int, N+1)
	deleted := make([]bool, N+1)

	INF := int64(1e16)
	V[0] = INF
	V[N] = INF
	L[0] = -1
	R[0] = 1
	L[N] = N - 1
	R[N] = -1

	pq := make(PQ, 0, N)

	for i := 1; i < N; i++ {
		V[i] = T[i] - T[i-1]
		L[i] = i - 1
		R[i] = i + 1
		heap.Push(&pq, Item{V[i], i})
	}

	var ans int64 = 0

	for step := 0; step < K; step++ {
		var minItem Item
		for {
			minItem = heap.Pop(&pq).(Item)
			if !deleted[minItem.i] && minItem.v == V[minItem.i] {
				break
			}
		}

		idx := minItem.i
		ans += V[idx]

		left := L[idx]
		right := R[idx]

		V[idx] = V[left] + V[right] - V[idx]
		deleted[left] = true
		deleted[right] = true

		L[idx] = L[left]
		if L[idx] != -1 {
			R[L[idx]] = idx
		}

		R[idx] = R[right]
		if R[idx] != -1 {
			L[R[idx]] = idx
		}

		heap.Push(&pq, Item{V[idx], idx})
	}

	fmt.Println(ans)
}