CP Hack Tools

My Programming Template

#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>

#define eb emplace_back
#define fi first 
#define se second 
#define mp make_pair
#define mt make_tuple
#define tm ((tl+tr)>>1)
#define INF (1<<62)
#define endl "\n"
#define mem(v,w) memset(v,w,sizeof(v))
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ub upper_bound
#define lb lower_bound
#define vi vector<int>
#define si stack<int>
#define vvi vector<vector<int>>
#define setbits(v) __builtin_popcount(v)
#define setbitsll(v) __builtin_popcountll(v)
#define nth_element(s,n) *(s.find_by_order(n-1)) 
#define count_smaller(s,n) s.order_of_key(n)  
#define raffle_draw(l,r) uniform_int_distribution<int>(l,r)(prng)
#define log(...) cerr << __LINE__ << ": "; logger(#__VA_ARGS__,__VA_ARGS__)

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; //pbds

template <class T,class U> bool chmin(T &x, U y){ if(x>y){ x=y; return true; } return false; }
template <class T,class U> bool chmax(T &x, U y){ if(x<y){ x=y; return true; } return false; }

mt19937 prng(chrono::steady_clock::now().time_since_epoch().count()); // mersenne twister
const long double pi = acos(-1.0);
const int mod = 1e9+7;

/* logging utitlies */
template<typename ...Args>
void logger(string vars, Args&&... values){
	cerr << "[";
	cerr << vars << "] = ";
	string delimeter = "";
	cerr << "[";
		(..., (cerr <<  delimeter << values, delimeter=","));
	cerr << "]\n";
}

/* i/o stream utilities */
ostream& operator <<(ostream& out, pair<int,int> const& v){
    out << v.fi << "," << v.se; 
    return out; 
}

template<typename T>
ostream& operator <<(ostream& out, const vector<T>& v){
    for (const T& x: v) out << x << " "; 
    return out; 
}

template<typename T, typename S>
ostream& operator <<(ostream& out, const map<T,S>& v){
    for (auto& x: v) out << x.fi << "-->" << x.se; 
    return out; 
}

template<typename T>
ostream& operator <<(ostream& out, const set<T>& v){
    for (auto& x: v) cout << x << " ";
    return out;
}

template<typename T>
ostream& operator <<(ostream& out, const multiset<T>& v){
    for (auto& x: v) cout << x << " ";
    return out;
}

/* adhoc utilities */  
inline ll ceil_divide(ll a,ll b){   return (a+b-1)/b; }	

template <class T>
void remove_duplicates(vector<T> &v){ sort(all(v)); v.erase(unique(all(v)),v.end());}

string to_binary(ll v){
    if(!v) return "0";
    string s="";
    while (v>0){
        s += static_cast<char>(v%2 + '0');
        v/=2;
    }
    reverse(all(s));
    return s; 
    
}

int main(){
	
	std::ios::sync_with_stdio(false);
	cin.tie(0);

	#ifdef _INPUT
	freopen("input.txt", "r", stdin);
	#endif 

	return 0;
}

Stress Test PY Template

import filecmp
import os
import random
import sys
import subprocess

my_solution = sys.argv[1]
test_solution = sys.argv[2]

my_solution_exe = my_solution.split(".cpp")[0]
test_solution_exe = test_solution.split(".cpp")[0]

input_file = "in.txt"
my_solution_out = "out1.txt"
test_solution_out = "out2.txt"

def generate_input_file():
    '''
    Write code here to generate the input file
    Tips:
        1. Use random.randint(l,r) : to generate random number between l...r
        2. Perm = list(range(1,n)) random.shuffle(Perm) : to generate a randome permutation
    '''
    with open (input_file, "w") as f:
        N = 10
        M = 3
        f.write(f"{N} {M}\n")
        for i in range(M):
            K = random.randint(1,N) 
            C = random.randint(1,100)
            f.write (f"{K} {C}")
            f.write ("\n")
            
            lst = list(range(1,N+1))
            random.shuffle(lst)
            lst = lst [0:K]
            for j in lst:
                f.write (f"{j} ")

            f.write("\n")
    
def test_case(i):
    u  = generate_input_file()
    os.system(f"./{my_solution_exe} < {input_file} > {my_solution_out}")
    os.system(f"./{test_solution_exe} < {input_file} > {test_solution_out}")

    with open(my_solution_out, "r") as f:
        a = f.readline()
        a.rstrip()

    with open(test_solution_out, "r") as f:
        b = f.readline()
        b.rstrip()

    if a == b:
        print(f"Test {i} passed.")
    else:
        print("ERROR, match out1.txt and out2.txt.")
        sys.exit(0)

def run_commands(cmd):
    print(cmd)
    try:
        cmd = cmd.split(" ")
        subprocess.run(cmd, check=True)
    except subprocess.CalledProcessError as e:
        print ("Error:", e)

def compile_command(cpp_file):
    compilation_flags = "-std=c++17"
    exe_name = cpp_file.split(".cpp")[0]
    return f"g++ {compilation_flags} -o {exe_name} {cpp_file}"

if __name__ == '__main__':

    run_commands(compile_command(my_solution))
    run_commands(compile_command(test_solution))

    for i in range(1,100):
        test_case(i)

Combinatorics Template

inline int mul(int x,int y){    ll z = 1ll; z=z*x*y;   z%=mod; return (int)z; }
inline int add(int x,int y){    ll z = 0ll; z=z+x+y;   z%=mod; return (int)z; }
inline int sub(int x,int y){    ll z=0ll;   z=x+mod-y; z%=mod; return (int)z; }

inline int binpow(int x,int y){

    ll z = 1ll;
    while(y){
        if(y&1) z=mul(z,x);
        x = mul(x,x);
        y>>=1;
    }
    return (int)z;
}

inline int inv(int x){ return binpow(x,mod-2); }

const int N = 400004;
int fac[N], rfac[N];
void fasetup(){
	fac[0] = rfac[0] = 1;
	for(int i=1;i<N;i++) fac[i] = mul(fac[i-1],i);
	rfac[N-1] = inv(fac[N-1]);
	for(int i=N-2;i>0;i--) rfac[i] = mul(rfac[i+1], i+1);
} 

int choose(int n,int r){
	assert(n>=r);
	return mul(fac[n], mul(rfac[r],rfac[n-r])); 
}

Fenwick Tree Template

void update (int i, int val) {
    for (; i < N ; i+= i&-i) Fen[i] = max (Fen[i], val); 
}
int query (int r) {
    int Ans = 0; 
    for (; r > 0 ; r -= r&-r) Ans = max (Ans, Fen[r]);
    return Ans; 
}   

void cleanTree (int i) {
    for (; i<N; i += i&-i) Fen[i] = 0; 
}

Number Theory Template

vector<int> p; 
int sieve [MAXN]; 
auto sievef = [&] (int MAXN) -> void {
    sieve[1] = 1;
    for (int i = 2; i < MAXN; i++){
        if (sieve[i]) continue;
        p.emplace_back (i); 
        for (int j = i; j < MAXN; j += i){
            if (!sieve[j]) sieve [j] = i; 
        }
    }
};

auto factor = [&](int n) -> vector<pii> {
    vector<pii> res;
    for (int &x : p){
        if (x * x > n) break;
        else if (n % x) continue;
        res.emplace_back (x, 0); 
        while (n % x == 0) {
            res.back().se++; 
            n /= x; 
        } 
    }
    if (n > 1) res.emplace_back (n, 1); 
    return res; 
};

vi divisors (int n) {
    vi d = {1};
    while (n > 1){
        int m = 0;
        int q = sieve[n];
        while (n % q == 0) { m++; n /= q; }
        int dsize = d.size();
        int pw = q; 
        for (int i = 0;i < m; i++) {
            for (int j = 0; j < dsize; j++) d.emplace_back (d[j] * pw);
            pw *= q;
        } 
    }
    return d; 
} 

Disjoint Set Template

/* Usage: DSU S(n); S.unite (1, 2); S.totalSize(2); */

struct DSU {
	vector <int> par, size_;
	int biggest; 
	DSU (int n) : par (n+1), size_(n+1, 1), biggest(1) { 
		for (int i=0;i<=n;i++) par[i] = i;
	}
	int root (int u) {
		if (par[u] == u) return u; 
		return par[u] = root (par[u]);
	}
	void unite (int u, int v){
		int ru = root(u), rv = root(v); 
		if (ru == rv) return; 
		if (rand() & 1) swap (u, v); 
		size_[rv] += size_[ru];
		par[ru] = rv;
		chmax (biggest, size_[rv]); 	
	}

	int totalSize (int u) {
		return size_[root(u)]; 
	} 
};

Segment Tree Template

/* 1-based segment tree template */
// $set : infinite, ST_MAX, Node constructor, combine code


const int ST_MAX = <>;
int _array[ST_MAX];
const int infinite = <>;

struct Node{
    // 0. add node variables and constructors 
    // int node_variables;
	int val;	
	Node () {
		val = infinite; 
	} 
	Node (int val) : val (val) {} 
};

int _n; // $ set _n 
class SegmentTree {
    public:
		
        Node *_t;
    public:
        
        SegmentTree (int n) {
            _n = n;
            _t = new Node[_n*6]; 
        }

        Node combine (Node lc, Node rc){
            Node res;
            /* 1. add your combine code along with empty node  */
			if (lc.val == infinite) return rc; 
			else if (rc.val == infinite) return lc; 
			int va = max (lc.val, rc.val);  
            return Node (va);
        }

        Node query (const int& l, const int& r, int v=1, int tl=1, int tr=_n){
            if (r<tl||l>tr) return Node (); 
            if (tl>=l && tr<=r) return _t[v]; 
            return combine (query(l, r, v<<1, tl, tm), 
                query(l, r, v<<1|1, tm+1, tr));
        }

        void build (int v=1, int tl=1, int tr=_n){
            if (tl==tr) _t[v] = Node(_array[tl]); 
            else {
                build (v<<1, tl, tm);
                build (v<<1|1, tm+1, tr); 
                _t[v] = combine (_t[v<<1], _t[v<<1|1]); 
            }
        }

        // point update 
        void update (const int& pos, const int& val, int v=1, int tl=1, int tr=_n){
            if (tl==tr) _t[v] = Node(val);  
            else {
                if (pos <= tm) update (pos, val, v<<1, tl, tm);
                else update (pos, val, v<<1|1, tm+1, tr); 
                _t[v] = combine (_t[v<<1], _t[v<<1|1]);  
            }
        }
};
/* Segment Tree tested*/

Hashing Template

struct HashInt {
	static const int mx=1e9+7, my=1e9+9;
	long long x, y;
	HashInt () = default;
	HashInt (long long x_) : x(x_), y(x_) {}
	HashInt (long long x_, long long y_) : x(x_), y(y_) {}
	HashInt operator + (const HashInt& other) const{
		HashInt tmp; 
		tmp.x = (x + other.x) % mx;
		tmp.y = (y + other.y) % my;
		return tmp;
	}
	HashInt operator - (const HashInt& other) const{
		HashInt tmp; 
		tmp.x = (mx + x - other.x) % mx;
		tmp.y = (my + y - other.y) % my; 		
		return tmp;
	}
	HashInt operator * (const HashInt& other) const{
		HashInt tmp; 
		tmp.x = (x * other.x) % mx;
		tmp.y = (y * other.y) % my; 		
		return tmp;
	}
	bool operator == (const HashInt& other) const{
		return x == other.x && y == other.y;
	}
	operator pair<long long ,long long> () const {
		return make_pair (x, y);
	}
}; 

namespace RollHash{
	const int P=239017, N_ = 9e5+4;
	HashInt p[N_], H[N_];
	<always call init before initializing test cases> 
	void init() { 
		p[0] = 1;
		for (int i=1;i<N_;i++){
			p[i] = p[i-1] * P; 
		}
	}
	void gen_hashes (const string& str){
		int n = str.size();
		H[0] = str[0];
		for (int i=1;i<n;i++){
			H[i] = H[i-1] * P + str[i];
		}
	}
		
	HashInt hasher (int l, int r) { return l ? H[r] - H[l-1] * p[r-l+1] : H[r]; }
};

using namespace RollHash;

Sliding Window Template

for(int l=0,r=-1;l<n;l++){ // left boundary of the sliding window
	r = max(r, l-1);
	while(r+1 < n){
		/* modify the window*/
		if extendible? 
			r++;
		else 
			/* rollback window  */ 
		break;

		if(chmax(max_length, r-l+1)){
			// record answer from window
		}
	}
	// modify window to delete left boundary to proceed to the next, l++ happens
}

MO Query Template

int B; 

struct Query{

	int l, r, idx; 
	pair<int, int> toPair () const {
		int b = l/B; 
		return {b, (b&1)?-r:r};
	}
	bool operator < (const Query& other) {
		return toPair () < other.toPair();
	}
};

long long curr = 0; 
void add (int); 
void remove (int);

void solve_offline (vector<Query> q) {
	sort (all(q));
	int currL = 1, currR = 1;
	add (arr[1]); 	
	for (int Q: q){
		int L,R,idx; 
		while (L < currL) add (arr[--currL]);	
		while (R > currR) add (arr[++currR]);
		while (L > currL) remove (arr[currL++]); 
		while (R < currR) remove (arr[currR--]);
		answer[idx] = curr;
	}
} 

Ordered Set Template

	struct RBTree { 
	typedef tree<pii, 
			null_type, 
			less<pii>,
			rb_tree_tag, 
			tree_order_statistics_node_update> ord;
	ord s;
	int _t;
	
	RBTree() {  
		_t = 0;
	}
	void emplace (int x) { s.insert ({x, ++_t});  }
	void erase (int x) { s.erase (s.lower_bound({x, 0})); }
	int less_than (int x) { return s.order_of_key({x, 0}); }
	int less_eq (int x) { return s.order_of_key({x+1, 0}); }
	int find_nth (int n) { 
		if (s.find_by_order(n) == s.end()) return -1;
		return s.find_by_order(n)->first;
	}
};	

Double Precision Arithmetic

const double EPS = 1e-9;
bool chequal (double a, double b) {
    return abs (a - b) < EPS; 
}

double L2norm (pair<double, double> a, pair<double, double> b){ 
    return sqrt (pow(a.fi - b.fi, 2) + pow(a.se - b.se, 2)); 
}

cout << setprecision (12) << fixed; 