GCJ/2017/Qualification/C/main.go

package main

import (
	"container/heap"
	"fmt"
)

func main() {
	var T, N, K int
	fmt.Scan(&T)
	for cid := 1; cid <= T; cid++ { // Too slow for large dataset
		println("Case", cid)
		fmt.Printf("Case #%d: ", cid)
		fmt.Scan(&N)
		fmt.Scan(&K)
		if K == N {
			fmt.Printf("0 0\n")
			continue
		} else if K == 1 {
			fmt.Printf("%d %d\n", N/2, N-N/2-1)
			continue
		}
		var pq PQ
		heap.Push(&pq, N/2)
		heap.Push(&pq, N-N/2-1)
		for i := 1; i < K-1; i++ {
			stall := heap.Pop(&pq).(int)
			heap.Push(&pq, stall/2)
			heap.Push(&pq, stall-stall/2-1)
		}
		stall := heap.Pop(&pq).(int)
		fmt.Printf("%d %d\n", stall/2, stall-stall/2-1)
	}
}

// PQ ...
type PQ struct {
	queue  []int
	length int
}

func (pq PQ) Len() int           { return pq.length }
func (pq PQ) Less(i, j int) bool { return pq.queue[j] < pq.queue[i] }
func (pq PQ) Swap(i, j int)      { pq.queue[i], pq.queue[j] = pq.queue[j], pq.queue[i] }

// Push ...
func (pq *PQ) Push(x interface{}) {
	pq.queue = append(pq.queue, x.(int))
	pq.length++
}

// Pop ...
func (pq *PQ) Pop() interface{} {
	pq.length--
	top := pq.queue[pq.length]
	pq.queue = pq.queue[:pq.length]
	return top
}