← Home
For problem statement at 1000-1999/1700-1799/1720-1729/1728/problemF.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1720-1729/1728/verifierF.go ends with case 1 failed: expected 1 got 0
input:
1
exit status 1 can you fix the verifier? package main

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

type Item struct {
	val int
	idx int
}

type MinHeap []Item

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].val < h[j].val }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Item))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n int
	if _, err := fmt.Fscan(reader, &n); err != nil {
		return
	}
	a := make([]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Fscan(reader, &a[i])
	}

	owner := make(map[int]int)
	matched_val := make(map[int]int)

	for i := 1; i <= n; i++ {
		pq := &MinHeap{}
		heap.Init(pq)
		heap.Push(pq, Item{val: a[i], idx: i})

		visited := make(map[int]bool)
		parent := make(map[int]int)

		for pq.Len() > 0 {
			curr := heap.Pop(pq).(Item)
			val := curr.val
			idx := curr.idx

			if visited[val] {
				heap.Push(pq, Item{val: val + a[idx], idx: idx})
				continue
			}

			visited[val] = true
			parent[val] = idx

			if owner_idx, exists := owner[val]; exists {
				heap.Push(pq, Item{val: a[owner_idx], idx: owner_idx})
				heap.Push(pq, Item{val: val + a[idx], idx: idx})
			} else {
				curr_val := val
				for {
					j := parent[curr_val]
					if j == i {
						owner[curr_val] = i
						matched_val[i] = curr_val
						break
					}
					prev_val := matched_val[j]
					owner[curr_val] = j
					matched_val[j] = curr_val
					curr_val = prev_val
				}
				break
			}
		}
	}

	sum := int64(0)
	for _, val := range matched_val {
		sum += int64(val)
	}
	fmt.Println(sum)
}