snippets.txt

Table of Contents:

#sp #tests
#o1d #o2d #tie #i1d #ixy #i2d
#iadjlist
#comp #bridges_and_cutpoints #kruskal
#dsu
#powm #gcd #er #matrix
#forin #forim #forjn #forjm #forinr
#shi #ninj
#bits #popcnt #gosper
#limits #int128 #M #PI
#unique
#intiterator
#now #debug
#modular
#binsearch
#geometry
#rle
#kuhn
================================================================================
// #sp
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <utility>
using namespace std;

int main() {
    $end$
}

================================================================================
// #tests
int tests;
cin >> tests;
for (int test = 1; test <= tests; ++test) {
    $end$
    cout << "Case #" << test << ": " << solve(ARG) << endl;
}
================================================================================
// #o1d
for (int i = 0; i < n; ++i) {
    cout << a[i] << " ";
}
cout << endl;
$end$
================================================================================
// #o2d
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        cout << a[i][j] << " ";
    }
    cout << endl;
}
cout << endl;
$end$
================================================================================
// #tie
cin.tie(0);
cin.sync_with_stdio(false);
cout.tie(0);
cout.sync_with_stdio(false);
$end$
================================================================================
// #i1d
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
    cin >> a[i];
}
$end$
================================================================================
// #ixy
int n;
cin >> n;
vector<int> x(n), y(n);
for (int i = 0; i < n; ++i) {
    cin >> x[i] >> y[i];
}
$end$
================================================================================
// #i2d
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        cin >> a[i][j];
    }
}
$end$
================================================================================
// #iadjlist
int n, m;
cin >> n >> m;
vector<vector<int>> adjlist(n);
for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v; --u; --v;
    adjlist[u].push_back(v);
    adjlist[v].push_back(u);
}
$end$
================================================================================
// #comp
vector<int> front;
int ncomp = 0;
vector<int> comp(n, -1);
for (int i = 0; i < n; ++i) {
    if (comp[i] == -1) {
        comp[i] = ncomp;
        ++ncomp;
        front = {i};
        for (int j = 0; j < front.size(); ++j) {
            int v = front[j];
            for (int nn : adj[v]) {
                if (comp[nn] == -1) {
                    comp[nn] = comp[v];
                    front.push_back(nn);
                }
            }
        }
    }
}
$end$
================================================================================
// #bridges_and_cutpoints
void bridges_dfs(
    int V, vector<vector<pair<int, int>>> const& adjlist_edge,
    int v, int from,
    vector<bool>& used, vector<int>& timein, vector<int>& fup, int& timer,
    vector<bool>& result_bridge, vector<bool>& result_cutpoint
) {
    used[v] = true;
    timein[v] = fup[v] = timer++;
    int nchild = 0;
    for (auto [to, e] : adjlist_edge[v]) {
        if (to != from) {
            if (used[to]) {
                fup[v] = min(fup[v], timein[to]);
            } else {
                bridges_dfs(V, adjlist_edge, to, v, used, timein, fup, timer, result_bridge, result_cutpoint);
                fup[v] = min(fup[v], fup[to]);
                if (fup[to] > timein[v]) { result_bridge[e] = true; }
                if (fup[to] >= timein[v] && from != -1) { result_cutpoint[v] = true; }
                ++nchild;
            }
        }
    }
    if (from == -1 && nchild > 1) {
        result_cutpoint[v] = true;
    }
}

pair<vector<bool>, vector<bool>> bridges_and_cutpoint(
    int V, int E, vector<vector<pair<int, int>>> const& adjlist_edge
) {
    vector<bool> used(V), result_bridge(E), result_cutpoint(V);
    vector<int> timein(V), fup(V);
    int timer = 0;
    for (int i = 0; i < V; ++i) {
        if (!used[i]) {
            bridges_dfs(V, adjlist_edge, i, -1, used, timein, fup, timer, result_bridge, result_cutpoint);
        }
    }
    return {result_bridge, result_cutpoint};
}

$end$
================================================================================
// #kruskal
vector<int> kruskal(vector<int> const& u, vector<int> const& v, vector<double> const& w) {
    int E = u.size();
    int V = max(*max_element(u.begin(), u.end()), *max_element(v.begin(), v.end())) + 1;
    vector<int> edges(E); iota(edges.begin(), edges.end(), 0);
    sort(edges.begin(), edges.end(), [&w](int i, int j) { return w[i] < w[j]; });
    dsu d(V);
    vector<int> result; result.reserve(V - 1);
    for (int i = 0; i < E && (int) result.size() + 1 < V; ++i) {
        int uu = u[edges[i]], vv = v[edges[i]];
        if (d.find(uu) != d.find(vv)) {
            d.join(uu, vv);
            result.push_back(edges[i]);
        }
    }
    return result;
}

$end$
================================================================================
// #dsu
struct dsu {
    vector<int> parent, size;
    explicit dsu(int n) : parent(n), size(n, 1) { iota(parent.begin(), parent.end(), 0); }
    void join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            if (size[a] < size[b]) { swap(a, b); }
            parent[b] = a;
            size[a] += size[b];
        }
    }
    int find(int a) {
        if (parent[a] == a) { return a; }
        return parent[a] = find(parent[a]);
    }
};

$end$
================================================================================
// #powm
int powm(int a, int n, int M) {
    int64_t result = 1, p = a;
    while (n) {
        if (n & 1) {
            (result *= p) %= M;
        }
        (p *= p) %= M;
        n /= 2;
    }
    return (int) result;
}
================================================================================
// #gcd
template<typename T>
T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}
$end$
================================================================================
// #er
int const UP = 100000;
vector<int8_t> er(UP + 1);
er[0] = er[1] = 1;
for (int i = 2; i * i <= UP; ++i) {
    if (er[i] == 0) {
        for (int j = i * i; j <= UP; j += i) {
            er[j] = 1;
        }
    }
}
$end$
================================================================================
// #matrix
vector<vector<int>> mmul(int n, vector<vector<int>> const& a, vector<vector<int>> const& b) {
    vector<vector<int>> result(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                (result[i][j] += int64_t(a[i][k]) * b[k][j] % M) %= M;
            }
        }
    }
    return result;
}

vector<vector<int>> mpow(int n, vector<vector<int>> a, int64_t power) {
    vector<vector<int>> result(n, vector<int>(n));
    for (int i = 0; i < n; ++i) { result[i][i] = 1; }
    while (power) {
        if (power & 1) {
            result = mmul(n, result, a);
        }
        a = mmul(n, a, a);
        power /= 2;
    }
    return result;
}
$end$
================================================================================
// #forin
for (int i = 0; i < n; ++i) {
    $end$
}
================================================================================
// #forim
for (int i = 0; i < m; ++i) {
    $end$
}
================================================================================
// #forjn
for (int j = 0; j < n; ++j) {
    $end$
}
================================================================================
// #forjm
for (int j = 0; j < m; ++j) {
    $end$
}
================================================================================
// #forinr
for (int i = n - 1; i > 0; --i) {
    $end$
}
================================================================================
// #pii
pair<int, int> $end$
================================================================================
// #vvi
vector<vector<int>> $end$
================================================================================
// #vvl
vector<vector<int64_t>> $end$
================================================================================
// #vi
vector<int> $end$
================================================================================
// #vs
vector<string> $end$
================================================================================
// #vl
vector<int64_t> $end$
================================================================================
// #shi
int const shi[] = {-1, 0, 1, 0}, shj[] = {0, 1, 0, -1};
================================================================================
// #ninj
for (int dir = 0; dir < 4; ++dir) {
    int ni = i + shi[dir], nj = j + shj[dir];
    if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
        $end$
    }
}
================================================================================
// #bits
for (int mask = 0; mask < (1 << n); ++mask) {
    for (int bit = 0; bit < n; ++bit) {
        if ((mask >> bit) & 1) {
            $end$
        }
    }
}
================================================================================
// #popcnt
#if defined(_MSC_VER)
#include <intrin.h>
#define popcount __popcnt
#define popcount64 __popcnt64
#elif defined(__GNUC__)
#define popcount __builtin_popcount
#define popcount64 __builtin_popcountll
#endif

#if defined(_MSC_VER)
#include <intrin.h>
int clz(uint32_t x) { unsigned long result = -1; _BitScanReverse(&result, x); return 31 - result; }
int ctz(uint32_t x) { unsigned long result = -1; _BitScanForward(&result, x); return result; }
int clz64(uint64_t x) { unsigned long result = -1; _BitScanReverse64(&result, x); return 63 - result; }
int ctz64(uint64_t x) { unsigned long result = -1; _BitScanForward64(&result, x); return result; }
#elif defined(__GNUC__)
#define clz __builtin_clz
#define ctz __builtin_ctz
#define clz64 __builtin_clzll
#define ctz64 __builtin_ctzll
#endif
$end$
================================================================================
// #gosper
int set = (1 << k) - 1;
int limit = (1 << n);
while (set < limit) {
    $end$

    int c = set & -set;
    int r = set + c;
    set = (((r ^ set) >> 2) / c) | r;
}
================================================================================
// #limits
int const IMAX = numeric_limits<int>::max();
int const IMIN = numeric_limits<int>::min();
int64_t const LMAX = numeric_limits<int64_t>::max();
int64_t const LMIN = numeric_limits<int64_t>::min();
$end$
================================================================================
// #int128
#if defined(_MSC_VER)
#include <boost/multiprecision/cpp_int.hpp>
typedef boost::multiprecision::int128_t int128_t;
#elif defined(__GNUC__)
typedef __int128 int128_t;
#endif
$end$
================================================================================
// #M
int const M = 1000000007;
$end$
================================================================================
// #PI
double const PI = 3.14159265358979323;
$end$
================================================================================
// #unique
a.erase(unique(a.begin(), a.end()), a.end());
$end$
================================================================================
// #intiterator
template<typename TInt, typename TFn>
struct int_iterator : iterator<random_access_iterator_tag, TInt> {
    TInt n;
    TFn *PPred = nullptr;
    int_iterator(TInt n, TFn& pred) : n(n), PPred(&pred) { }
    TInt operator * () const { return (*PPred)(n); }
    operator TInt() const { return n; }
    int_iterator& operator ++ () { return *this += 1; }
    int_iterator& operator += (TInt rhs) { n += rhs; return *this; }
};
template<typename TInt, typename TFn>
int_iterator<TFn> make_int_iterator(TInt n, TFn& pred) {
    return int_iterator<TInt, TFn>(n, pred);
}
$end$
================================================================================
// #now
auto t0 = chrono::high_resolution_clock::now();

$selected$$end$

auto t1 = chrono::high_resolution_clock::now();
cerr << chrono::duration_cast<chrono::duration<double>>(t1 - t0).count() << " s" << endl;
================================================================================
// #debug
#ifndef ONLINE_JUDGE

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(char const *x) { cerr << '\"' << x << '\"'; }
void __print(string const& x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template<typename T, typename V>
void __print(pair<T, V> const& x) { cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}'; }
template<int... Is, typename... Ts>
void __print(tuple<Ts...> const& x, integer_sequence<size_t, Is...> tag) {
    int dummy[] = {((Is ? (cerr << ",", 0) : 0), __print(get<Is>(x)), 0)...};
}
template<typename... Ts>
void __print(tuple<Ts...> const& x) { cerr << '{'; __print(x, make_index_sequence<sizeof...(Ts)>{}); cerr << '}'; }
template<typename T>
void __print(T const& x) { int f = 0; cerr << '{'; for (auto& i : x) { cerr << (f++ ? "," : ""), __print(i); } cerr << "}"; }

template<typename T>
void _print_name(char const *name, T&& t) { cerr << name << " = "; __print(t); cerr << "\n"; }
template<typename T, typename... V>
void _print_name(char const *name, T&& t, V&&... v) {
    cerr << name << " = "; __print(forward<T>(t));
    if (sizeof...(v)) { cerr << "  "; }
    _print_name(forward<V>(v)...);
}

#define debug_1(x1)                     _print_name(#x1, x1)
#define debug_2(x1, x2)                 _print_name(#x1, x1, #x2, x2)
#define debug_3(x1, x2, x3)             _print_name(#x1, x1, #x2, x2, #x3, x3)
#define debug_4(x1, x2, x3, x4)         _print_name(#x1, x1, #x2, x2, #x3, x3, #x4, x4)
#define debug_5(x1, x2, x3, x4, x5)     _print_name(#x1, x1, #x2, x2, #x3, x3, #x4, x4, #x5, x5)
#define debug_6(x1, x2, x3, x4, x5, x6) _print_name(#x1, x1, #x2, x2, #x3, x3, #x4, x4, #x5, x5, #x6, x6)

// use 'Zc:preprocessor' in MSVC
#define CAT_(a, b) a ## b
#define CAT(a, b) CAT_(a, b)
#define NARGS(...)  INTERNAL_EXPAND_ARGS_PRIVATE(INTERNAL_ARGS_AUGMENTER(__VA_ARGS__))
#define INTERNAL_ARGS_AUGMENTER(...) unused, __VA_ARGS__
#define INTERNAL_EXPAND(x) x
#define INTERNAL_EXPAND_ARGS_PRIVATE(...) INTERNAL_EXPAND(INTERNAL_GET_ARG_COUNT_PRIVATE(__VA_ARGS__, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0))
#define INTERNAL_GET_ARG_COUNT_PRIVATE(_1_, _2_, _3_, _4_, _5_, _6_, _7_, _8_, _9_, _10_, _11_, _12_, _13_, _14_, _15_, _16_, _17_, _18_, _19_, _20_, count, ...) count

#define debug(...) do { CAT(debug_, NARGS(__VA_ARGS__))(__VA_ARGS__); } while (0)

#else
#define debug(...)
#endif
$end$
================================================================================
// #modular
template<int M>
class Z {
    int v = 0;

    static int inv(int a, int m) {
        a %= m;
        return a == 1 ? 1 : int(m - int64_t(inv(m, a)) * m / a);
    }

public:
    Z(int64_t v_) : v(int(v_ % M)) { if (v < 0) { v += M; } }
    explicit operator int() const { return v; }
    bool operator == (Z const& rhs) { return v == rhs.v; }
    bool operator != (Z const& rhs) { return v != rhs.v; }

    Z inv() const { return {inv(v, M)}; }
    Z operator - () const { return {v ? M - v : 0}; }
    Z& operator ++ () { ++v; if (v == M) { v = 0; } return *this; }
    Z& operator -- () { --v; if (v < 0) { v += M; } return *this; }
    Z& operator += (Z const& rhs) { v -= M - rhs.v; if (v < 0) { v += M; } return *this; }
    Z& operator -= (Z const& rhs) { v -= rhs.v; if (v < 0) { v += M; } return *this; }
    Z& operator *= (Z const& rhs) { v = int(int64_t(v) * rhs.v % M); return *this; }
    Z& operator /= (Z const& rhs) { return *this *= rhs.inv(); }

    friend Z operator + (Z const& lhs, Z const& rhs) { return Z(lhs) += rhs; }
    friend Z operator - (Z const& lhs, Z const& rhs) { return Z(lhs) -= rhs; }
    friend Z operator * (Z const& lhs, Z const& rhs) { return Z(lhs) *= rhs; }
    friend Z operator / (Z const& lhs, Z const& rhs) { return Z(lhs) /= rhs; }

    friend ostream& operator << (ostream& out, Z const& rhs) { return out << rhs.v; }
    friend ostream& operator >> (istream& in, Z& rhs) { int v_; in >> v_; rhs = Z(v_); return in; }
};

template<typename T>
T pow(T a, int64_t p) {
    T result = 1;
    while (p) {
        if (p & 1) {
            result *= a;
        }
        p /= 2;
        a *= a;
    }
    return result;
}

int const M = 1000000007;
using num = Z<M>;

$end$
================================================================================
// #binsearch
int64_t lo = 0, hi = 1000000000000000000;
auto satisfy = [&](int64_t x) {
    return x > 42;$end$
};
while (lo < hi) {
    int64_t mid = lo + (hi - lo) / 2;
    satisfy(mid) ? hi = mid : lo = mid + 1;
}
return lo; // lo - lowest value that satisfy
================================================================================
// #geometry
double det2(double a11, double a12, double a21, double a22) { return a11 * a22 - a12 * a21; }

struct vec2 {
    double x, y;
    vec2(double x_, double y_) : x(x_), y(y_) { }
};

bool operator == (vec2 v, vec2 w) { return v.x == w.x && v.y == w.y; }
vec2 operator / (vec2 v, double d) { return {v.x / d, v.y / d}; }
vec2 operator * (vec2 v, double d) { return {v.x * d, v.y * d}; }
vec2 operator + (vec2 v, vec2 w) { return {v.x + w.x, v.y + w.y}; }
vec2 operator - (vec2 v, vec2 w) { return {v.x - w.x, v.y - w.y}; }
double len(vec2 v) { return hypot(v.x, v.y); }
vec2 cross(vec2 x1, vec2 v1, vec2 x2, vec2 v2) {
    double t1 = det2(x2.x - x1.x, -v2.x, x2.y - x1.y, -v2.y) / det2(v1.x, -v2.x, v1.y, -v2.y);
    return x1 + v1 * t1;
}

$end$
================================================================================
// #rle

int cur = 0;
for (int i = 0; i < n; ++i) {
	++cur;
	if (i + 1 == n || a[i] != a[i + 1]) {
		$end$yield(cur, a[i]);
		cur = 0;
	}
}
================================================================================
// #kuhn
bool try_kuhn(int v, vector<vector<int>> const& adjlist, vector<char>& used, vector<int>& mt) {
	if (used[v]) { return false; }
	used[v] = true;
	for (int to : adjlist[v]) {
		if (mt[to] == -1 || try_kuhn(mt[to], adjlist, used, mt)) {
			mt[to] = v;
			return true;
		}
	}
	return false;
}

vector<pair<int, int>> kuhn(int npart1, int npart2, vector<vector<int>> const& adjlist) {
	vector<char> used(npart1), used1(npart1);
	vector<int> mt(npart2, -1);

	for (int i = 0; i < npart1; ++i) {
		for (int to : adjlist[i]) {
			if (mt[to] == -1) {
				mt[to] = i;
				used1[i] = true;
				break;
			}
		}
	}

	for (int i = 0; i < npart1; ++i) {
		if (used1[i]) { continue; }
		used.assign(npart1, false);
		try_kuhn(i, adjlist, used, mt);
	}

	vector<pair<int, int>> result;
	for (int i = 0; i < npart2; ++i) {
		if (mt[i] != -1) {
			result.emplace_back(mt[i], i);
		}
	}
	return result;
}

$end$
================================================================================
// #cumsum
template<typename T>
vector<T> cumsum(vector<T> const& a) {
	size_t n = a.size();
	vector<T> result(n + 1);
	for (int i = 0; i < n; ++i) {
		result[i + 1] = result[i] + a[i];
	}
	return result;
}
$end$
================================================================================
// #dp
template<typename T> bool updmax(T& lhs, T const& rhs) { if (rhs > lhs) { lhs = rhs; return true; } return false; }
template<typename T> bool updmin(T& lhs, T const& rhs) { if (rhs < lhs) { lhs = rhs; return true; } return false; }
template<typename T> bool updmaxeq(T& lhs, T const& rhs) { if (rhs >= lhs) { lhs = rhs; return true; } return false; }
template<typename T> bool updmineq(T& lhs, T const& rhs) { if (rhs <= lhs) { lhs = rhs; return true; } return false; }
template<typename T> bool updmax(T& lhs, T const& rhs, T const& guard) { if (lhs == guard || rhs > lhs) { lhs = rhs; return true; } return false; }
template<typename T> bool updmin(T& lhs, T const& rhs, T const& guard) { if (lhs == guard || rhs < lhs) { lhs = rhs; return true; } return false; }
template<typename T> bool updmaxeq(T& lhs, T const& rhs, T const& guard) { if (lhs == guard || rhs >= lhs) { lhs = rhs; return true; } return false; }
template<typename T> bool updmineq(T& lhs, T const& rhs, T const& guard) { if (lhs == guard || rhs <= lhs) { lhs = rhs; return true; } return false; }

template<typename T, size_t N> struct make_nd_type { using type = vector<typename make_nd_type<T, N - 1>::type>; };
template<typename T> struct make_nd_type<T, 0> { using type = T; };
template<typename T, size_t N> using make_nd_t = typename make_nd_type<T, N>::type;
template<typename T> auto make_nd(T&& value) -> T { return value; }
template<typename T, typename... TArgs>
auto make_nd(T&& value, size_t index, TArgs... indices) -> make_nd_t<T, 1 + sizeof...(TArgs)> {
    static_assert(conjunction_v<is_convertible<TArgs, size_t>...>);
    return make_nd_t<T, 1 + sizeof...(TArgs)>(index, make_nd<T>(forward<T>(value), indices...));
}
$end$
================================================================================
// #stack_codeforces
#pragma comment(linker, "/STACK:268435456")
================================================================================