Templates

Fast I/O

• Fast I/O

  C++

  Turn off sync with stdio and untie cin from cout. Use this as the main() shell on every C++ file.

  Copy

  #include <bits/stdc++.h>
  using namespace std;
  
  int main() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
  
      int n;
      if (!(cin >> n)) return 0;
      vector<long long> a(n);
      for (int i = 0; i < n; i++) cin >> a[i];
  
      // solve...
      cout << 0 << "\n";
      return 0;
  }
  

• Fast I/O

  Python

  Read the whole stdin buffer once and tokenize. Faster than input() in a loop at 2e5+ tokens.

  Copy

  import sys
  
  _data = sys.stdin.buffer.read().split()
  _it = iter(_data)
  
  def read():
      return next(_it)
  
  def read_int():
      return int(read())
  
  def main():
      n = read_int()
      a = [read_int() for _ in range(n)]
      # solve...
      sys.stdout.write("0\n")
  
  if __name__ == "__main__":
      main()
  

• Fast I/O

  JS

  Node contest runner: slurp stdin, split on whitespace, pull tokens with an index pointer.

  Copy

  const fs = require("fs");
  const tokens = fs.readFileSync(0, "utf8").trim().split(/\s+/);
  let p = 0;
  const next = () => tokens[p++];
  const nextInt = () => Number(next());
  
  function main() {
    const n = nextInt();
    const a = Array.from({ length: n }, () => nextInt());
    // solve...
    console.log(0);
  }
  
  main();
  

DSU / Union-Find

• DSU / Union-Find

  C++

  Path compression + union by size. find is O(α(n)). 0-indexed; pass n = vertex count.

  Copy

  #include <bits/stdc++.h>
  using namespace std;
  
  struct DSU {
      vector<int> p, sz;
      DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
      int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
      bool same(int a, int b) { return find(a) == find(b); }
      int size(int x) { return sz[find(x)]; }
      bool unite(int a, int b) {
          a = find(a);
          b = find(b);
          if (a == b) return false;
          if (sz[a] < sz[b]) swap(a, b);
          p[b] = a;
          sz[a] += sz[b];
          return true;
      }
  };
  

• DSU / Union-Find

  Python

  Iterative find with path halving so Python does not blow the recursion limit at n = 1e6.

  Copy

  class DSU:
      def __init__(self, n):
          self.p = list(range(n))
          self.sz = [1] * n
  
      def find(self, x):
          while self.p[x] != x:
              self.p[x] = self.p[self.p[x]]
              x = self.p[x]
          return x
  
      def same(self, a, b):
          return self.find(a) == self.find(b)
  
      def size(self, x):
          return self.sz[self.find(x)]
  
      def unite(self, a, b):
          a, b = self.find(a), self.find(b)
          if a == b:
              return False
          if self.sz[a] < self.sz[b]:
              a, b = b, a
          self.p[b] = a
          self.sz[a] += self.sz[b]
          return True
  

• DSU / Union-Find

  JS

  Same structure as the C++ DSU. unite returns whether the merge created a new link.

  Copy

  class DSU {
    constructor(n) {
      this.p = Array.from({ length: n }, (_, i) => i);
      this.sz = Array(n).fill(1);
    }
    find(x) {
      while (this.p[x] !== x) {
        this.p[x] = this.p[this.p[x]];
        x = this.p[x];
      }
      return x;
    }
    same(a, b) {
      return this.find(a) === this.find(b);
    }
    size(x) {
      return this.sz[this.find(x)];
    }
    unite(a, b) {
      a = this.find(a);
      b = this.find(b);
      if (a === b) return false;
      if (this.sz[a] < this.sz[b]) [a, b] = [b, a];
      this.p[b] = a;
      this.sz[a] += this.sz[b];
      return true;
    }
  }
  

Binary search · firstTrue

• Binary search · firstTrue

  C++

  Search [lo, hi). Invariant: !ok(lo-1) and ok(hi). Returns the first x where ok(x) is true, or hi if none.

  Copy

  #include <bits/stdc++.h>
  using namespace std;
  
  // ok is monotonic false* true*. Returns first x in [lo, hi] with ok(x); hi if none.
  template <class F>
  long long firstTrue(long long lo, long long hi, F ok) {
      while (lo < hi) {
          long long mid = lo + (hi - lo) / 2;
          if (ok(mid)) hi = mid;
          else lo = mid + 1;
      }
      return lo;
  }
  
  // Example: minimum capacity that ships all weights in D days.
  long long shipWithinDays(const vector<int>& weights, int D) {
      auto ok = [&](long long cap) {
          int days = 1;
          long long load = 0;
          for (int w : weights) {
              if (load + w > cap) {
                  days++;
                  load = 0;
              }
              load += w;
          }
          return days <= D;
      };
      long long lo = *max_element(weights.begin(), weights.end());
      long long hi = accumulate(weights.begin(), weights.end(), 0LL) + 1;
      return firstTrue(lo, hi, ok);
  }
  

• Binary search · firstTrue

  Python

  Same [lo, hi) invariant as the C++ template. Pass a monotone predicate, not a sorted array.

  Copy

  def first_true(lo, hi, ok):
      # Search [lo, hi). Returns first x in [lo, hi] with ok(x), or hi if none.
      while lo < hi:
          mid = lo + (hi - lo) // 2
          if ok(mid):
              hi = mid
          else:
              lo = mid + 1
      return lo
  
  
  def ship_within_days(weights, D):
      def ok(cap):
          days, load = 1, 0
          for w in weights:
              if load + w > cap:
                  days += 1
                  load = 0
              load += w
          return days <= D
  
      lo = max(weights)
      hi = sum(weights) + 1
      return first_true(lo, hi, ok)
  

• Binary search · firstTrue

  JS

  The only binary search you need on a monotone predicate. Interval is [lo, hi).

  Copy

  // ok[i] is false* then true*. Return first index where ok(i) is true, or hi.
  function firstTrue(lo, hi, ok) {
    while (lo < hi) {
      const mid = lo + Math.floor((hi - lo) / 2);
      if (ok(mid)) hi = mid;
      else lo = mid + 1;
    }
    return lo;
  }
  
  function shipWithinDays(weights, D) {
    const ok = (cap) => {
      let days = 1;
      let load = 0;
      for (const w of weights) {
        if (load + w > cap) {
          days++;
          load = 0;
        }
        load += w;
      }
      return days <= D;
    };
    let lo = Math.max(...weights);
    let hi = weights.reduce((s, w) => s + w, 0) + 1;
    return firstTrue(lo, hi, ok);
  }
  

Binary search · lower bound

• Binary search · lower bound

  C++

  First index i with a[i] >= x on a sorted array. Same contract as std::lower_bound.

  Copy

  #include <bits/stdc++.h>
  using namespace std;
  
  // First i in [0, n] with a[i] >= x. Returns n if every a[i] < x.
  int lowerBound(const vector<int>& a, int x) {
      int lo = 0, hi = (int)a.size();
      while (lo < hi) {
          int mid = lo + (hi - lo) / 2;
          if (a[mid] >= x) hi = mid;
          else lo = mid + 1;
      }
      return lo;
  }
  
  // First i with a[i] > x (std::upper_bound).
  int upperBound(const vector<int>& a, int x) {
      int lo = 0, hi = (int)a.size();
      while (lo < hi) {
          int mid = lo + (hi - lo) / 2;
          if (a[mid] > x) hi = mid;
          else lo = mid + 1;
      }
      return lo;
  }
  

• Binary search · lower bound

  Python

  Handwritten bisect_left / bisect_right. Use this when you cannot import bisect, or to keep the invariant visible.

  Copy

  def lower_bound(a, x):
      lo, hi = 0, len(a)
      while lo < hi:
          mid = lo + (hi - lo) // 2
          if a[mid] >= x:
              hi = mid
          else:
              lo = mid + 1
      return lo
  
  
  def upper_bound(a, x):
      lo, hi = 0, len(a)
      while lo < hi:
          mid = lo + (hi - lo) // 2
          if a[mid] > x:
              hi = mid
          else:
              lo = mid + 1
      return lo
  

• Binary search · lower bound

  JS

  Lower bound is firstTrue on the predicate a[i] >= x. Upper bound flips to a[i] > x.

  Copy

  function lowerBound(a, x) {
    let lo = 0;
    let hi = a.length;
    while (lo < hi) {
      const mid = lo + Math.floor((hi - lo) / 2);
      if (a[mid] >= x) hi = mid;
      else lo = mid + 1;
    }
    return lo;
  }
  
  function upperBound(a, x) {
    let lo = 0;
    let hi = a.length;
    while (lo < hi) {
      const mid = lo + Math.floor((hi - lo) / 2);
      if (a[mid] > x) hi = mid;
      else lo = mid + 1;
    }
    return lo;
  }
  

Prefix sums

• Prefix sums

  C++

  1-indexed prefix so sum(l, r) inclusive on 0-based a is pref[r+1] - pref[l]. Build O(n), query O(1).

  Copy

  #include <bits/stdc++.h>
  using namespace std;
  
  vector<long long> buildPrefix(const vector<long long>& a) {
      int n = (int)a.size();
      vector<long long> pref(n + 1);
      for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + a[i];
      return pref;
  }
  
  // Inclusive range on 0-based a[l..r].
  long long rangeSum(const vector<long long>& pref, int l, int r) {
      return pref[r + 1] - pref[l];
  }
  

• Prefix sums

  Python

  1-indexed prefix list. range_sum(l, r) is inclusive on the original 0-based array.

  Copy

  def build_prefix(a):
      pref = [0] * (len(a) + 1)
      for i, x in enumerate(a):
          pref[i + 1] = pref[i] + x
      return pref
  
  
  def range_sum(pref, l, r):
      # Inclusive a[l..r], 0-based.
      return pref[r + 1] - pref[l]
  

• Prefix sums

  JS

  0-based running prefix matching the lesson: sum(l, r) = pref[r] - (l ? pref[l-1] : 0).

  Copy

  function buildPrefix(a) {
    const pref = new Array(a.length);
    let running = 0;
    for (let i = 0; i < a.length; i++) {
      running += a[i];
      pref[i] = running;
    }
    return pref;
  }
  
  function rangeSum(pref, l, r) {
    const left = l === 0 ? 0 : pref[l - 1];
    return pref[r] - left;
  }
  

BFS grid

• BFS grid skeleton

  C++

  4-direction BFS. Mark dist when you push, not when you pop. grid[r][c] == 1 is a wall; -1 means unreachable.

  Copy

  #include <bits/stdc++.h>
  using namespace std;
  
  const int DR[] = {1, -1, 0, 0};
  const int DC[] = {0, 0, 1, -1};
  
  vector<vector<int>> bfs(const vector<vector<int>>& grid, int sr, int sc) {
      int h = (int)grid.size(), w = (int)grid[0].size();
      vector<vector<int>> dist(h, vector<int>(w, -1));
      queue<pair<int, int>> q;
      dist[sr][sc] = 0;
      q.push({sr, sc});
      while (!q.empty()) {
          auto [r, c] = q.front();
          q.pop();
          for (int k = 0; k < 4; k++) {
              int nr = r + DR[k], nc = c + DC[k];
              if (nr < 0 || nc < 0 || nr >= h || nc >= w) continue;
              if (grid[nr][nc] == 1) continue;
              if (dist[nr][nc] != -1) continue;
              dist[nr][nc] = dist[r][c] + 1;
              q.push({nr, nc});
          }
      }
      return dist;
  }
  

• BFS grid skeleton

  Python

  collections.deque BFS on a grid. Same wall / dist convention as the C++ skeleton.

  Copy

  from collections import deque
  
  DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
  
  def bfs(grid, sr, sc):
      h, w = len(grid), len(grid[0])
      dist = [[-1] * w for _ in range(h)]
      dist[sr][sc] = 0
      q = deque([(sr, sc)])
      while q:
          r, c = q.popleft()
          for dr, dc in DIRS:
              nr, nc = r + dr, c + dc
              if nr < 0 or nc < 0 or nr >= h or nc >= w:
                  continue
              if grid[nr][nc] == 1:
                  continue
              if dist[nr][nc] != -1:
                  continue
              dist[nr][nc] = dist[r][c] + 1
              q.append((nr, nc))
      return dist
  

• BFS grid skeleton

  JS

  Index-pointer queue so shift() does not go quadratic. First visit is the shortest unweighted path.

  Copy

  const DIRS = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  
  function bfs(grid, sr, sc) {
    const h = grid.length;
    const w = grid[0].length;
    const dist = Array.from({ length: h }, () => Array(w).fill(-1));
    const q = [[sr, sc]];
    dist[sr][sc] = 0;
    for (let head = 0; head < q.length; head++) {
      const [r, c] = q[head];
      for (const [dr, dc] of DIRS) {
        const nr = r + dr;
        const nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= h || nc >= w) continue;
        if (grid[nr][nc] === 1) continue; // wall
        if (dist[nr][nc] !== -1) continue;
        dist[nr][nc] = dist[r][c] + 1;
        q.push([nr, nc]);
      }
    }
    return dist;
  }