Templates

Code Templates — Competitive Programming (Go)

1. Full Boilerplate

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var bw = bufio.NewWriter(os.Stdout)

func init() {
    sc.Split(bufio.ScanWords)
    sc.Buffer(make([]byte, 1<<20), 1<<20)
}

func nextInt() int {
    sc.Scan()
    v, _ := strconv.Atoi(sc.Text())
    return v
}

func nextString() string { sc.Scan(); return sc.Text() }

func min(a, b int) int { if a < b { return a }; return b }
func max(a, b int) int { if a > b { return a }; return b }

func main() {
    defer bw.Flush()
    t := nextInt()
    for ; t > 0; t-- {
        solve()
    }
}

func solve() {
    n := nextInt()
    // ... problem logic
    fmt.Fprintln(bw, "answer")
}

2. Modular Arithmetic

const MOD = 1000000007

func modAdd(a, b int64) int64 { return (a + b) % MOD }
func modSub(a, b int64) int64 { return (a - b + MOD) % MOD }
func modMul(a, b int64) int64 { return a * b % MOD }

func modPow(a, b int64) int64 {
    res := int64(1)
    a %= MOD
    for b > 0 {
        if b&1 == 1 { res = res * a % MOD }
        a = a * a % MOD
        b >>= 1
    }
    return res
}

func modInv(a int64) int64 { return modPow(a, MOD-2) }

3. DSU

type DSU struct { parent, size []int }
func NewDSU(n int) *DSU {
    p, s := make([]int, n), make([]int, n)
    for i := range p { p[i] = i; s[i] = 1 }
    return &DSU{p, s}
}
func (d *DSU) Find(x int) int {
    for d.parent[x] != x { d.parent[x] = d.parent[d.parent[x]]; x = d.parent[x] }
    return x
}
func (d *DSU) Union(a, b int) bool {
    a, b = d.Find(a), d.Find(b)
    if a == b { return false }
    if d.size[a] < d.size[b] { a, b = b, a }
    d.parent[b] = a; d.size[a] += d.size[b]
    return true
}

4. Fenwick Tree (BIT)

type BIT struct { tree []int }
func NewBIT(n int) *BIT { return &BIT{make([]int, n+1)} }
func (b *BIT) Add(idx, delta int) {
    for i := idx; i < len(b.tree); i += i & -i { b.tree[i] += delta }
}
func (b *BIT) Sum(idx int) int {
    res := 0
    for i := idx; i > 0; i -= i & -i { res += b.tree[i] }
    return res
}
func (b *BIT) RangeSum(l, r int) int { return b.Sum(r) - b.Sum(l-1) }

5. Dijkstra

import "container/heap"

type Edge struct{ to, w int }
type Item struct{ node, dist int }
type PQ []Item
func (h PQ) Len() int { return len(h) }
func (h PQ) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h *PQ) Push(x any) { *h = append(*h, x.(Item)) }
func (h *PQ) Pop() any { n := len(*h); x := (*h)[n-1]; *h = (*h)[:n-1]; return x }

func dijkstra(g [][]Edge, start int, n int) []int {
    INF := math.MaxInt32
    dist := make([]int, n)
    for i := range dist { dist[i] = INF }
    pq := &PQ{}
    heap.Push(pq, Item{start, 0})
    dist[start] = 0
    for pq.Len() > 0 {
        cur := heap.Pop(pq).(Item)
        if cur.dist > dist[cur.node] { continue }
        for _, e := range g[cur.node] {
            nd := cur.dist + e.w
            if nd < dist[e.to] { dist[e.to] = nd; heap.Push(pq, Item{e.to, nd}) }
        }
    }
    return dist
}

6. Input for Large Problems

For very large input (1M+ ints), use:

func nextInt() int {
    sc.Scan()
    v := 0
    for _, c := range sc.Bytes() { v = v*10 + int(c-'0') }
    return v
}

Avoid Atoi overhead when you know it's digits.

Templates