🏆
// ===============================================
// ICPC COMPLETE C++ CHEAT SHEET (ALGO + STL)
// ===============================================
#include <bits/stdc++.h> // Includes all standard C++ libraries
using namespace std;
// ---------- TYPEDEFS & MACROS ----------
#define ll long long // Shorthand for long long
#define pb push_back // Short alias for vector push_back
#define all(v) (v).begin(), (v).end() // Iterate entire container (ascending)
#define rall(v) (v).rbegin(), (v).rend() // Iterate entire container (descending)
#define ff first // Access first element of pair
#define ss second // Access second element of pair
#define endl '\n' // Faster newline (avoids flushing like std::endl)
🔁
// ==============================
// SHORT LOOP & CONDITIONAL MACROS
// ==============================
// Loop from 0 to n-1 (0-based loop)
#define rep(i, n) for (int i = 0; i < (n); i++)
// Loop from 1 to n (1-based loop)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
// Loop from n-1 down to 0 (reverse loop)
#define per(i, n) for (int i = (n) - 1; i >= 0; i--)
// Range-based loop (iterate directly over container elements)
#define each(x, v) for (auto &x : (v))
// Quick output for YES/NO answers
#define yes cout << "YES\n"
#define no cout << "NO\n"
rep(i, n) cin >> a[i]; // read n elements
rep1(i, n) sum += i; // sum from 1 to n
per(i, n) cout << a[i]; // print reverse
each(x, v) cout << x << " "; // print all elements
if (ok) yes; else no; // quick output
// ---------- FAST I/O ----------
#define fastio() ios::sync_with_stdio(false); [Link](NULL);
// Speeds up input/output operations (disable sync with C I/O + untie
cin/cout)
// ---------- CONSTANTS ----------
const ll MOD = 1e9 + 7; // Common modulus for modular arithmetic
const ll INF = 1e18; // Large value representing infinity (for Dijkstra,
DP, etc.)
// Find max/min in vector
int mx = *max_element(all(v));
int mn = *min_element(all(v));
// Count elements
int cnt = count(all(v), x);
// Range-based loop (C++11+)
for (int x : v);
// Loop with auto (works for any container)
for (auto &x : v);
// Ternary shorthand
int mx = (a > b ? a : b);
// Sum of vector
ll sum = accumulate(all(v), 0LL);
// Break / Continue inside loops
for (int i = 0; i < n; i++) {
if (a[i] < 0) continue;
if (a[i] == 0) break;
}
⚡
// ==============================
// FAST I/O TEMPLATE
// ==============================
void fast_io() { ios::sync_with_stdio(false); [Link](nullptr); }
🔍
// ==============================
// SEARCH & BASIC UTILS
// ==============================
int binarySearch(vector<int>& a, int x) {
int l = 0, r = [Link]() - 1;
while (l <= r) {
int m = (l + r) / 2;
if (a[m] == x)
return m;
if (a[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
// Prefix Sum / Sliding Window
vector<int> prefixSum(vector<int>& a) {
vector<int> p([Link]() + 1, 0);
for (int i = 0; i < [Link](); i++)
p[i + 1] = p[i] + a[i];
return p;
}
📊
// ==============================
// GRAPH ALGORITHMS
// ==============================
void bfs(int n, vector<vector<int>>& adj) {
vector<int> vis(n);
queue<int> q;
[Link](0);
vis[0] = 1;
while (![Link]()) {
int u = [Link]();
[Link]();
for (int v : adj[u]) {
if (!vis[v]) {
vis[v] = 1;
[Link](v);
}
}
}
}
vector<ll> dijkstra(int n, vector<vector<pair<int, int>>>& adj, int src) {
vector<ll> dist(n, INF);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
dist[src] = 0;
[Link]({0, src});
while (![Link]()) {
auto [d, u] = [Link]();
[Link]();
if (d != dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[v] > d + w) {
dist[v] = d + w;
[Link]({dist[v], v});
}
}
}
return dist;
}
struct DSU {
vector<int> p, sz;
DSU(int n) {
[Link](n);
[Link](n, 1);
iota([Link](), [Link](), 0);
}
int find(int x) {
return p[x] == x ? x : p[x] = find(p[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;
}
};
📐
// ==============================
// DYNAMIC PROGRAMMING
// ==============================
int LIS(vector<int>& a) {
vector<int> dp;
for (int x : a) {
auto it = lower_bound([Link](), [Link](), x);
if (it == [Link]())
dp.push_back(x);
else
*it = x;
}
return [Link]();
}
int knapsack(vector<int>& w, vector<int>& val, int W) {
int n = [Link]();
vector<int> dp(W + 1);
for (int i = 0; i < n; i++) {
for (int j = W; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j - w[i]] + val[i]);
}
}
return dp[W];
}
🔢
// ==============================
// NUMBER THEORY
// ==============================
// Fast Modular Exponentiation (Binary Exponentiation)
ll mod_pow(ll a, ll b, ll m) {
ll res = 1;
while (b) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
// Euclidean Algorithm for GCD
ll gcd_ll(ll a, ll b) {
return b ? gcd_ll(b, a % b) : a;
}
// Modular Multiplicative Inverse (using Fermat's Little Theorem)
ll mod_inv(ll a, ll m) {
return mod_pow(a, m - 2, m);
}
// Sieve of Eratosthenes (Prime Sieve)
vector<int> prime_sieve(int n) {
vector<int> is_prime(n + 1, 1);
is_prime[0] = is_prime[1] = 0;
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i)
is_prime[j] = 0;
}
}
return is_prime;
}
🔢
// ==============================
// NUMBER THEORY EXTENSIONS
// ==============================
// Least Common Multiple (using GCD)
ll lcm_ll(ll a, ll b) {
return a / gcd_ll(a, b) * b;
}
// Extended Euclidean Algorithm (for modular inverse when MOD not
prime)
ll extended_gcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
ll x1, y1;
ll g = extended_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return g;
}
// Modular Inverse (works for any m)
ll mod_inv_any(ll a, ll m) {
ll x, y;
ll g = extended_gcd(a, m, x, y);
if (g != 1) return -1; // inverse doesn't exist
return (x % m + m) % m;
}
// Simple Prime Check (O(√n))
bool is_prime(ll n) {
if (n < 2) return false;
for (ll i = 2; i * i <= n; i++)
if (n % i == 0) return false;
return true;
}
// Factorization (O(√n))
vector<ll> factors(ll n) {
vector<ll> f;
for (ll i = 1; i * i <= n; i++) {
if (n % i == 0) {
[Link](i);
if (i != n / i) [Link](n / i);
}
}
sort(all(f));
return f;
}
// Precompute factorials & modular inverses for nCr / nPr
const int MAXN = 1e6;
vector<ll> fact(MAXN + 1, 1), invfact(MAXN + 1, 1);
void precompute_fact() {
for (int i = 1; i <= MAXN; i++)
fact[i] = fact[i - 1] * i % MOD;
invfact[MAXN] = mod_pow(fact[MAXN], MOD - 2, MOD);
for (int i = MAXN - 1; i >= 0; i--)
invfact[i] = invfact[i + 1] * (i + 1) % MOD;
}
// nCr under modulo (Fermat)
ll nCr(int n, int r) {
if (r < 0 || r > n) return 0;
return fact[n] * invfact[r] % MOD * invfact[n - r] % MOD;
}
// nPr under modulo
ll nPr(int n, int r) {
if (r < 0 || r > n) return 0;
return fact[n] * invfact[n - r] % MOD;
}
// Modular addition / subtraction / multiplication
inline ll addmod(ll a, ll b, ll m = MOD) { return (a + b) % m; }
inline ll submod(ll a, ll b, ll m = MOD) { return (a - b + m) % m; }
inline ll mulmod(ll a, ll b, ll m = MOD) { return (a * b) % m; }
🔡
// ==============================
// STRING ALGORITHMS
// ==============================
// Prefix Function (KMP Failure Function)
vector<int> prefix_function(const string& s) {
int n = [Link]();
vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j])
j = pi[j - 1];
if (s[i] == s[j])
j++;
pi[i] = j;
}
return pi;
}
// Z-Function (Z Algorithm)
vector<int> z_function(const string& s) {
int n = [Link]();
vector<int> z(n);
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
if (i <= r)
z[i] = min(r - i + 1, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
z[i]++;
if (i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
return z;
}
🧩
// ==============================
// DATA STRUCTURES
// ==============================
// Segment Tree (Range Sum Query)
struct SegTree {
int n;
vector<ll> t;
SegTree(int n) : n(n) {
[Link](4 * n, 0);
}
void build(vector<ll>& a, int v, int tl, int tr) {
if (tl == tr) {
t[v] = a[tl];
return;
}
int tm = (tl + tr) / 2;
build(a, v * 2, tl, tm);
build(a, v * 2 + 1, tm + 1, tr);
t[v] = t[v * 2] + t[v * 2 + 1];
}
ll sum(int v, int tl, int tr, int l, int r) {
if (l > r)
return 0;
if (l == tl && r == tr)
return t[v];
int tm = (tl + tr) / 2;
return sum(v * 2, tl, tm, l, min(r, tm))
+ sum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
}
};
// Fenwick Tree (Binary Indexed Tree)
struct Fenwick {
int n;
vector<ll> bit;
Fenwick(int n) : n(n) {
[Link](n + 1, 0);
}
// Add value to index i
void add(int i, ll val) {
for (; i <= n; i += i & -i)
bit[i] += val;
}
// Prefix sum up to index i
ll sum(int i) {
ll s = 0;
for (; i > 0; i -= i & -i)
s += bit[i];
return s;
}
};
🧰
// ==============================
// STL QUICK REFERENCE (WITH COMMENTS)
// ==============================
// ---------- VECTOR ----------
vector<int> v = {1, 2, 3}; // Declare and initialize vector
v.push_back(4); // Add element at end
v.pop_back(); // Remove last element
sort([Link](), [Link]()); // Sort in ascending order
reverse([Link](), [Link]()); // Reverse the vector
// ---------- PAIR & TUPLE ----------
pair<int, int> p = {1, 2}; // Create a pair
auto [x, y] = p; // Structured binding (C++17)
tuple<int, int, int> t = {1, 2, 3}; // Create a tuple
auto [a, b, c] = t; // Structured binding for tuple
// ---------- STACK / QUEUE / DEQUE ----------
stack<int> st; // LIFO stack
queue<int> q; // FIFO queue
deque<int> dq; // Double-ended queue
[Link](1); // Push element into stack
[Link](2); // Push element into queue
dq.push_front(3); // Push element to front of deque
// ---------- PRIORITY QUEUE ----------
priority_queue<int> maxpq; // Max-heap (default)
priority_queue<int, vector<int>, greater<>> minpq; // Min-heap
[Link](10); // Insert element
[Link](); // Get max element
[Link](); // Remove max element
// ---------- SET / MAP / MULTISET ----------
set<int> s = {1, 3, 5}; // Ordered unique elements
[Link](2); // Insert element
multiset<int> ms; // Allows duplicates
[Link](1);
map<int, string> mp; // Key-value pairs (ordered by key)
mp[1] = "one";
unordered_map<int, int> um; // Hash map (O(1) average)
um[1] = 100;
// ---------- BITSET ----------
bitset<8> b("10110010"); // Fixed-size bit array (8 bits)
[Link](); // Number of bits set to 1
[Link](2); // Toggle bit at index 2 (0-based)
// ---------- ALGORITHMS ----------
sort([Link](), [Link]()); // Sort ascending
reverse([Link](), [Link]()); // Reverse order
lower_bound([Link](), [Link](), x); // First pos >= x (binary search)
upper_bound([Link](), [Link](), x); // First pos > x (binary search)
accumulate([Link](), [Link](), 0); // Sum of elements
count([Link](), [Link](), val); // Count occurrences of val
next_permutation([Link](), [Link]()); // Rearrange to next lexicographic
order
rotate([Link](), [Link]() + 1, [Link]()); // Rotate left by one position
// ---------- STRING UTILITIES ----------
string s = "gaurav";
reverse([Link](), [Link]()); // Reverse string
[Link](1, 3); // Substring from index 1 of length 3
[Link]("ra"); // Find position of substring
to_string(123); // Convert int → string
stoi("456"); // Convert string → int
// ---------- BUILTIN FUNCTIONS ----------
__gcd(a, b); // Greatest common divisor
__builtin_popcount(x); // Number of set bits in int
__builtin_clz(x); // Count leading zeros
__builtin_ctz(x); // Count trailing zeros
// ---------- ITERATORS ----------
auto it = [Link](); // Iterator to first element
advance(it, 2); // Move iterator forward by 2
distance([Link](), it); // Compute distance between iterators
⚙️
// ==============================
// CONTEST REMINDERS
✅
// ==============================
✅
// Check constraints before choosing algorithm
✅
// Watch for overflows; use long long
✅
// Handle edge cases: empty input, 1-element
✅
// Re-init visited/DP for multiple testcases
✅
// Prefer iterative DP to avoid stack overflow
✅
// Always test with small custom cases first
✅
// Use fast I/O for large input sizes
// Use modulo ops consistently when required