On this page
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.