CP Cheat Sheet

#include <bits/stdc++.h> // Imports all standard C++ libraries


using namespace std;     // Avoids writing std:: everywhere

// Macros for fast coding
#define ll long long int // Shorthand for long long

int main() {
// Fast I/O (Unlinks C++ streams from C stdio for maximum speed)
ios_base::sync_with_stdio(false);
cin.tie(NULL);

cout << "Hello World!" << "\n"; // Use "\n" over 'endl' (endl triggers costly flushing)
return 0;


}

// Limits and shorthand definitions


int max_int = INT_MAX;       // Approx: 2 * 10^9
int min_int = INT_MIN;       // Approx: -2 * 10^9
long long max_ll = LLONG_MAX; // Approx: 9 * 10^18
long long min_ll = LLONG_MIN;

const int MOD = 1e9 + 7;     // Standard modulo prime

// Modular arithmetic wrappers to prevent code overflow
long long safe_add(long long a, long long b) {
return (a % MOD + b % MOD) % MOD;
}

long long safe_sub(long long a, long long b) {
return (a % MOD - b % MOD + MOD) % MOD;
}

long long safe_mul(long long a, long long b) {
return ((a % MOD) * (b % MOD)) % MOD;
}

// 1D Vector operations


vector v;
v.push_back(10); // Adds element to tail. v = {10}
v.push_back(20); // v = {10, 20}
int sz = v.size(); // Retrieves length: 2
int last = v.back(); // References last item: 20
v.pop_back(); // Trims last element. v = {10}

// Initialize vector of size 10 pre-filled with zero
vector zeroes(10, 0);

// --- 2D Matrix (N x M filled with 0s) ---
int N = 5, M = 6;
vector> matrix2D(N, vector(M, 0));
// Access syntax: matrix2D[row][col] = value;

// --- 3D Matrix (X x Y x Z filled with 0s) ---
int X = 3, Y = 4, Z = 5;
vector>> matrix3D(X, vector>(Y, vector(Z, 0)));
// Access syntax: matrix3D[x][y][z] = value;

// Standard Queue (First-In, First-Out - FIFO)


queue q;
q.push(10);           // Adds to back
q.push(20);           // State: [10 (front), 20 (back)]
int first = q.front(); // Accesses oldest element (10)
q.pop();              // Removes 10 -> State: [20]

// Deque (Double-Ended Queue)
// O(1) insertion/deletion at both ends
deque dq;
dq.push_back(100);   // [100]
dq.push_front(50);   // [50, 100]
dq.push_back(150);   // [50, 100, 150]

int back_val = dq.back();    // Retrieves 150
int front_val = dq.front();  // Retrieves 50

dq.pop_front();  // Removes 50 -> State: [100, 150]
dq.pop_back();   // Removes 150 -> State: [100]
// Supports random access: dq[0] returns 100

// Stack (Last-In, First-Out - LIFO)


stack st;
st.push(5);        // [5]
st.push(10);       // State: [5, 10 (top)]
int tp = st.top(); // Retrieves top element (10)
st.pop();          // Removes 10 -> State: [5]

// Priority Queue (Max-Heap: Largest element on top, insertions in O(log N))
priority_queue max_heap;
max_heap.push(5);
max_heap.push(20);
max_heap.push(10);
int best = max_heap.top(); // Returns 20
max_heap.pop();            // Removes 20

// Min-Heap (Smallest element on top, insertions in O(log N))
priority_queue, greater> min_heap;
min_heap.push(5);
min_heap.push(20);
min_heap.push(1);
int smallest = min_heap.top(); // Returns 1

// 1. Pair (Binds two heterogeneous values)


pair p = {1, "apple"};
int key = p.first;
string val = p.second;

// 2. Set (Maintains sorted, distinct items. O(log N) lookup)
set s;
s.insert(10);
s.insert(10); // Ignored automatically
if (s.count(10)) { /* Key verification */ }

// 3. Map (Sorted key-value mapping. O(log N) lookup)
map m;
m[1] = "hello";

// 4. Unordered Map (Hash-table structure. Average O(1) lookup)
unordered_map umap;
umap[42] = 100;

// IMPORTANT: Custom Anti-Hash functor for unordered_map
// Protects unordered_map from O(N^2) malicious tests (hash collisions) on platforms like Codeforces
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
unordered_map safe_map;

vector<int> arr = {4, 1, 9, 3};


// --- SORTING ---
// Ascending Sort: {1, 3, 4, 9}
sort(arr.begin(), arr.end());

// Descending Sort
sort(arr.rbegin(), arr.rend());

// Custom Comparator (Lambda inline)
sort(arr.begin(), arr.end(), [](int x, int y) {
return x > y; // Descending rule
});

// --- MATH ---
int maximum = max(10, 20); // 20
int minimum = min(10, 20); // 10
int greatest_common_divisor = std::gcd(12, 18); // 6 (Requires C++17)

// --- BITWISE BUILT-INS (Translated directly to assembly instructions) ---
int set_bits = __builtin_popcount(15);        // Popcount of 32-bit integer (15 = 1111) -> 4
int set_bits_ll = __builtin_popcountll(15LL); // Popcount for 64-bit variables
int lead_zeros = __builtin_clz(16);           // Count leading zeros of a 32-bit int

vector<int> v = {10, 20, 30, 30, 30, 40, 50};


// 1. binary_search (Returns boolean check of existence)
bool found = binary_search(v.begin(), v.end(), 30); // true

// 2. lower_bound (Returns iterator to the FIRST element >= target)
auto lb = lower_bound(v.begin(), v.end(), 30);
int lb_idx = lb - v.begin(); // Subtract base iterator to fetch index -> 2

// 3. upper_bound (Returns iterator to the FIRST element > target)
auto ub = upper_bound(v.begin(), v.end(), 30);
int ub_idx = ub - v.begin(); // Subtract base iterator to fetch index -> 5

// Frequency trick: occurrences of '30' = (ub - lb) -> 3

// --- 1. Struct Implementation (Common in CP because fields are public by default) ---


struct ListNode {
int val;
ListNode* next;
// Quick Constructor
ListNode(int x) : val(x), next(nullptr) {}
};

// --- 2. Class Implementation (Standard Object-Oriented style) ---
class ClassNode {
public:
int val;
ClassNode* next;
ClassNode(int x) {
val = x;
next = nullptr;
}
};

// --- BASIC OPERATIONS DEMONSTRATION ---
void runListDemo() {
// Instantiation
ListNode* head = new ListNode(1);
head->next = new ListNode(2);

// Iterative Traversal
ListNode* curr = head;
while(curr != nullptr) {
    cout << curr->val << " ";
    curr = curr->next;
}

// Manual Deallocation (Memory Cleanup)
curr = head;
while(curr != nullptr) {
    ListNode* next_node = curr->next;
    delete curr; // Free memory of active pointer
    curr = next_node;
}


}

// 1. Pass by mutable reference (&) to directly alter external structures


void modifyVector(vector& v, map& hashmap) {
v.push_back(42);       // Modifies original vector
hashmap[1] = 100;      // Modifies original map
}

// 2. Pass by 'const reference' for read-only safety with O(1) memory overhead
void printHugeMatrix(const vector>& matrix) {
// matrix[0][0] = 5; // Compilation error! Read-only
cout << matrix.size() << "\n";
}

// 3. Pass Linked List using simple pointer (copies pointer address, not the structure)
void traverseList(ListNode* head) {
ListNode* curr = head;
while (curr != nullptr) {
curr = curr->next;
}
}

// 4. Updating the parent pointer itself requires pointer by reference
void pushToHead(ListNode*& head, int value) {
ListNode* new_head = new ListNode(value);
new_head->next = head;
head = new_head; // Directly updates parent's head reference
}