Competitive programming snippets

my_toolbox.h

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<ll>;

static constexpr ll M = 1e9 + 7;
static constexpr ll MM = 20170123456789LL;
static constexpr ll MMM = 9999999900000001LL;
static constexpr double PI = 3.14159265358979323846;

template <typename T> constexpr int inof(const T x) { return static_cast<int>(x); }
template <typename T> constexpr int sz(const T &xs) { return inof(xs.size()); }

template <typename T> constexpr ll llof(const T x) { return static_cast<ll>(x); }
template <typename T> constexpr double doof(const T x) { return static_cast<double>(x); }
constexpr char chof(const int x) { return static_cast<char>(x); }

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cout << setprecision(9) << fixed;

    return 0;
}

void ordered_set_in_action() {
    ordered_set<pair<int, string>> xs;
    for (int i = 0; i < 10; ++i) {
        xs.insert({i, to_string(i) + "li"});
    }
    
    const int i = 5;
    const auto back_it = xs.rbegin();
    const int hi = back_it->first;

    const auto it = xs.find_by_order(i);
    assert(xs.order_of_key(*it) == i);
    const string ans = it->second;
    xs.erase(it);
    xs.insert({hi + 1, ans});
}

template <typename T> ostream &operator<<(ostream &os, const optional<T> o) {
    if (!o) {
        os << "nullopt";
    } else {
        os << *o;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &x) {
    os << '(' << x.first << ' ' << x.second << ')';
    return os;
}

template <typename T> ostream &operator<<(ostream &os, const vector<T> &xs) {
    os << '[';
    for (auto i = xs.cbegin(); i != xs.cend(); ++i) {
        if (i != xs.cbegin()) os << ' ';
        os << *i;
    }
    os << ']';
    return os;
}

template <typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &xss) {
    for (const auto &xs : xss) os << xs << '\n';
    return os;
}

template <typename T> ostream &operator<<(ostream &os, const set<T> &xs) {
    os << '{';
    for (auto i = xs.cbegin(); i != xs.cend(); ++i) {
        if (i != xs.cbegin()) os << ' ';
        os << *i;
    }
    os << '}';
    return os;
}

template <typename K, typename V>
ostream &operator<<(ostream &os, const map<K, V> &m) {
    os << '{';
    for (auto i = m.cbegin(); i != m.cend(); ++i) {
        if (i != m.cbegin()) os << ' ';
        os << '(' << i->first << ' ' << i->second << ')';
    }
    os << '}';
    return os;
}

ostream &operator<<(ostream &os, const vector<string> &xss) {
    for (const auto &xs : xss) os << xs << '\n';
    return os;
}

template <typename T>
vector<T> compressed(const vector<T> &xs) {
    map<T, int> value_indices;    
    vector<T> result(size(xs));

    transform(cbegin(xs), cend(xs), begin(result), [&](const T x) -> int {
        const auto it = value_indices.find(x);
        if (it == cend(value_indices)) {
            value_indices.emplace(x, ssize(value_indices));
            return ssize(value_indices) - 1;
        } else {
            return it->second;
        }
    });

    return result;
}

vector<string> split(const string &delim_regex, const string &s) {
    regex r(delim_regex);
    return vector<string>(sregex_token_iterator(cbegin(s), cend(s), r, -1),
                          sregex_token_iterator{});
}

template <typename T>
string join(const string &glue, const vector<T> &tokens) {
    string ans;

    for (const auto &t : tokens) {
        if (!ans.empty()) ans += glue;
        ans += to_string(t);
    }

    return ans;
}

vector<string> static_re_matches(const string &pattern_str,
                                 const string &input) {
    static const regex pattern{pattern_str};
    smatch m;
    regex_match(input, m, pattern);
    assert(!empty(m));

    vector<string> result(size(m) - 1);
    transform(cbegin(m) + 1, cend(m), begin(result),
              [](const auto &x) { return x.str(); });
    return result;
}

template <typename T> vector<vector<T>> precompute_binomials(const int maxn) {
    vector<vector<T>> C(maxn + 1, vector<T>(maxn + 1, 0));
    C[0][0] = 1;

    for (int n = 1; n <= maxn; ++n) {
        C[n][0] = 1;
        C[n][n] = 1;
        for (int k = 1; k < n; ++k) {
            C[n][k] = C[n - 1][k - 1] + C[n - 1][k];
        }
    }

    return C;
}

template <typename T>
vector<vector<T>> cartesian_product(const vector<vector<T>> &src) {
    vector<vector<T>> result;
    if (src.empty() || any_of(cbegin(src), cend(src),
                              [](const auto &xs) { return xs.empty(); })) {
        return result;
    }

    result.push_back(vector<T>{});
    for (const auto &xs : src) {
        vector<vector<T>> next_gen;

        for (const auto x : xs) {
            for (auto curr : result) {
                curr.push_back(x);
                next_gen.push_back(curr);
            }
        }

        result = next_gen;
    }

    return result;
}

template <typename T> T immediately_under(const set<T> &xs, const T &x, const T &when_missing) {
    auto it = xs.lower_bound(x);
    return it == xs.cbegin() ? when_missing : *(--it);
}

template <typename K, typename V> V immediately_under(const map<K, V> &xxs, const K &k, const V &when_missing) {
    auto it = xxs.lower_bound(k);
    return it == xxs.cbegin() ? when_missing : (--it)->second;
}

template <typename T> struct mmin final {
    constexpr T operator()(const T &a, const T &b) const {
        return std::min(a, b);
    }
};

template <typename T> struct mmax final {
    constexpr T operator()(const T &a, const T &b) const {
        return std::max(a, b);
    }
};

template <typename Iter, typename R, typename Binop, typename Unaop>
R ttransform_reduce(Iter first, Iter last, R init, Binop binop, Unaop unaop) {
    return inner_product(first, last, first, init, binop,
                         [&unaop](const auto &x,
                                  __attribute__((unused))
                                  const auto &x_) { return unaop(x); });
}

template <typename T1, typename T2> struct PairHash final {
    size_t operator()(const pair<T1, T2> &p) const {
        return 31 * hash<T1>{}(p.first) + hash<T2>{}(p.second);
    }
};

template <typename T> size_t combine_hashes(const T &xs) {
    size_t seed = xs.size();

    for (const auto i : xs) 
        seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);

    return seed;
}

template <typename T> struct RndInt final {
    RndInt(const T lo, const T hi) : m_gen{random_device{}()}, m_dist{lo, hi} {}
    T next() { return m_dist(m_gen); }

  private:
    mt19937 m_gen;
    uniform_int_distribution<T> m_dist;
};

template <typename T>
constexpr pair<T, T> operator+(const pair<T, T> a, const pair<T, T> b) {
    return {a.first + b.first, a.second + b.second};
}

template <typename T>
constexpr T operator+(T a, const T &b) {
    assert(a.size() == b.size());
    transform(cbegin(a), cend(a), cbegin(b), begin(a), [](const auto x, const auto y) { return x + y; });
    return a;
}

using Coord = complex<int>;
constexpr int row(const Coord coord) { return coord.real(); } 
constexpr int col(const Coord coord) { return coord.imag(); }

struct CoordLess final {
    bool operator()(const Coord &a, const Coord &b) const {
        return (row(a) == row(b)) ? (col(a) < col(b)) : (row(a) < row(b));
    }
};

enum class Dir { Up, Right, Down, Left };
static constexpr array Delta{Coord{-1, 0}, Coord{0, 1}, Coord{1, 0},
                             Coord{0, -1}};

constexpr Dir dir_of(const Coord delta) {
    const int i = static_cast<int>(ranges::find(Delta, delta) - cbegin(Delta));
    assert(0 <= 1 && i < ssize(Delta));
    return static_cast<Dir>(i);
}

constexpr Coord delta_of(const Dir dir) {
    const int i = static_cast<int>(dir);
    assert(0 <= i && i < ssize(Delta));
    return Delta[i];
}

using lll = __int128_t;
using ulll = __uint128_t;

ostream &operator<<(ostream &dest, const lll value) {
    ostream::sentry s(dest);
    if (s) {
        ulll tmp = value < 0 ? -value : value;
        char buffer[128];
        char *d = end(buffer);

        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);

        if (value < 0) {
            --d;
            *d = '-';
        }

        const int len = static_cast<int>(end(buffer) - d);
        if (dest.rdbuf()->sputn(d, len) != len) dest.setstate(ios_base::badbit);
    }
    return dest;
}

// works for at least up to (2**31 - 1)**2
ll integer_sqrt_floor (const ll x) {
    ll result{};
    for (ll k = 1LL << 30; k != 0LL; k /= 2LL) {
        if ((result + k) * (result + k) <= x) {
            result += k;
        }
    }
    return result;
}

constexpr int mlog2(const ull x) {
    return 8 * sizeof(ull) - __builtin_clzll(x) - 1;
}

template <typename T> constexpr T div_ceil(const T x, const T y) {
    return x ? (1 + (x - 1) / y) : 0;
}

template <typename T> vector<int> digits_reversed(T n) {
    vector<int> ans;

    while (n) {
        ans.push_back(inof(n % static_cast<T>(10)));
        n /= static_cast<T>(10);
    }

    return ans;
}

template <typename T> vector<int> digits(T n) {
    auto ans = digits_reversed(n);
    reverse(begin(ans), end(ans));
    return ans;
}

template <typename T> T number(const vector<int> &ds) {
    if (ds.empty()) return 0;

    T ans = 0;
    T mul = 1;
    for (auto it = ds.crbegin(); it != ds.crend(); ++it) {
        ans += (*it) * mul;
        mul *= static_cast<T>(10);
    }
    return ans;
}

void remove_leading_zeros(vector<int> &ds) {
    for (auto it = ds.begin(); it != ds.end();) {
        if (*it != 0) break;
        it = ds.erase(it);
    }
}

static constexpr int AZ = 26;
constexpr int az_to_i(const char c) {
    return static_cast<int>(c) - static_cast<int>('a');
}
constexpr char i_to_az(const int i) {
    return static_cast<char>(static_cast<int>('a') + i);
}
constexpr int AZ_to_i(const char c) {
    return static_cast<int>(c) - static_cast<int>('A');
}
constexpr char i_to_AZ(const int i) {
    return static_cast<char>(static_cast<int>('A') + i);
}

snippets.rs

use std::io::{self, BufRead};
use regex::Regex;

fn all_tokens(src: &str) -> Vec<String> {
    Regex::new(r"[a-z0-9]+")
        .unwrap()
        .find_iter(src)
        .map(|x| x.as_str().to_string())
        .collect()
}

fn parse_token(src: &str) -> i32 {
    let re = Regex::new(r"^Guard #(\d+) begins shift$").unwrap();
    let caps = re.captures(src).unwrap();
    caps[1].parse().unwrap()
}

fn decode_particle(src: &str) -> (i32, {
    let re = Regex::new("^p=<(.+)>, v=<(.+)>, a=<(.+)>$").unwrap();
    let caps = re.captures(src).unwrap();
    let [p, v, a] = caps
        .iter()
        .skip(1)
        .map(|c| decode_triple(c.unwrap().as_str()))
        .collect::<Vec<_>>()[..]
    else {
        panic!("Not enough captured")
    };
    Particle { p, v, a }
}

#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
struct Crd(i32, i32);

impl std::ops::Add<Crd> for Crd {
    type Output = Crd;

    fn add(self, o: Crd) -> Crd {
        Crd(self.0 + o.0, self.1 + o.1)
    }
}

#[derive(Clone, Copy, Debug)]
enum Dir {
    N,
    E,
    S,
    W,
}

impl Dir {
    fn delta(&self) -> Crd {
        match self {
            Dir::N => Crd(-1, 0),
            Dir::E => Crd(0, 1),
            Dir::S => Crd(1, 0),
            Dir::W => Crd(0, -1),
        }
    }

    fn turn_left(&self) -> Dir {
        match self {
            Dir::N => Dir::W,
            Dir::E => Dir::N,
            Dir::S => Dir::E,
            Dir::W => Dir::S,
        }
    }

    fn turn_right(&self) -> Dir {
        match self {
            Dir::N => Dir::E,
            Dir::E => Dir::S,
            Dir::S => Dir::W,
            Dir::W => Dir::N,
        }
    }
}

fn transpose<T>(grid: Vec<Vec<T>>) -> Vec<Vec<T>> {
    assert!(!grid.is_empty());
    let h = grid[0].len();
    let mut iters: Vec<_> = grid.into_iter().map(|n| n.into_iter()).collect();
    (0..h)
        .map(|_| {
            iters
                .iter_mut()
                .map(|n| n.next().unwrap())
                .collect::<Vec<T>>()
        })
        .collect()
}

fn main() {
    let grid: Vec<Vec<char>> = io::stdin()
        .lock()
        .lines()
        .map(|line| line.unwrap().chars().collect())
        .collect();
}