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 candidate runtime error on test 40: exit status 2
Input used:
3 5
311911698 76203700 525458263 90724824 148941462
panic: runtime error: index out of range [-1]
goroutine 1 [running]:
main.main()
/tmp/cf-worker-1277218865/main.go:111 +0x520 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)
}