Miscellaneous Utilities API - C++ Algorithm Snippets

Overview

Miscellaneous utilities and helper functions for competitive programming including debugging tools, bit manipulation, coordinate compression, and various utility functions.

Debugging

Comprehensive debugging utilities adapted from tourist’s library (Gennady Korotkevich).

// Automatically disabled in online judges
#ifndef ONLINE_JUDGE
#define debug(...) writer_out << "[" << #__VA_ARGS__ << "]: [" , debug_out(__VA_ARGS__)
#define log(...) writer_out << "[" << #__VA_ARGS__ << "]: [" , debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#define log(...) 42
#endif

Supported Types:

Primitives: int, long long, char, bool, string
Containers: vector, set, map, unordered_map, queue, stack, priority_queue
Pairs and tuples
Custom types with to_string overload

Usage Example:

vector<int> arr = {1, 2, 3, 4, 5};
map<string, int> mp = {{"a", 1}, {"b", 2}};

debug(arr);        // [arr]: [{1, 2, 3, 4, 5}]
debug(mp);         // [mp]: [{(a, 1), (b, 2)}]
debug(arr, mp);    // [arr, mp]: [{1, 2, 3, 4, 5}] [{(a, 1), (b, 2)}]

Bit Manipulation

Efficient bit operations using GCC built-in functions.

Basic Bit Operations

int zeros_left(int num);    // Count leading zeros
int zeros_right(int num);   // Count trailing zeros
int count_ones(int num);    // Count set bits (popcount)
int parity(int num);        // Parity (1 if odd number of set bits)
int LSB(int num);           // Position of least significant bit

// 64-bit versions
int64_t zeros_left(int64_t num);
int64_t zeros_right(int64_t num);
int64_t count_ones(int64_t num);
int64_t parity(int64_t num);
int64_t LSB(int64_t num);

Hamming Distance

template<typename T>
int hamming(const T &lhs, const T &rhs);

Usage Example:

int a = 0b1010;
int b = 0b1100;
int dist = hamming(a, b);  // 2 (bits differ at positions 1 and 2)

Bit Tricks Cheat Sheet

// Check if x is odd
x & 1

// Check if i-th bit is set
x & (1 << i)

// Set i-th bit to 1
x = x | (1 << i)

// Set i-th bit to 0
x = x & ~(1 << i)

// Flip i-th bit
x = x ^ (1 << i)

// Flip all bits
x = ~x

// Get rightmost set bit (as power of 2)
x & -x

// Get position of rightmost set bit
log2(x & -x)

// Clear rightmost set bit
x = x & (x - 1)

// Set rightmost unset bit
x = x | (x + 1)

// Clear bits in x that are set in y
x = x & ~y

Iterate Over Set Bits

// O(number of set bits)
for (int x = mask; x; x &= x - 1) {
    int i = __builtin_ctz(x);  // Position of rightmost set bit
    // Process bit at position i
}

Iterate Over Submasks

// O(2^(number of set bits))
// Total complexity for all masks: O(3^n)
for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // Process submask
}

Coordinate Compression

Maps large coordinate values to smaller indices.

template<typename T>
struct CoordinateCompression {
    vector<T> coord;
    
    CoordinateCompression(vector<T> &v);
    int get_index(T value);
};

template<typename T>
using CC = CoordinateCompression<T>;

Usage Example:

vector<int> values = {100, 5000, 1000000, 500};
CC<int> cc(values);

int idx1 = cc.get_index(100);      // 0
int idx2 = cc.get_index(500);      // 1
int idx3 = cc.get_index(5000);     // 2
int idx4 = cc.get_index(1000000);  // 3

Complexity: O(n log n) construction, O(log n) per query

Y-Combinator

Enables lambda recursion in C++.

template<class Fun>
class y_combinator_result {
    Fun funct;
public:
    template<class T>
    explicit y_combinator_result(T &&fun);
    
    template<class ...Args>
    decltype(auto) operator()(Args &&...args);
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun);

Usage Example:

// Recursive DFS using lambda
auto dfs = y_combinator([&](auto dfs, int node, int parent) -> void {
    visited[node] = true;
    for(int child : adj[node]) {
        if(child != parent) {
            dfs(child, node);
        }
    }
});

dfs(0, -1);

// Fibonacci using Y-combinator
auto fib = y_combinator([&](auto fib, int n) -> int64_t {
    if(n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
});

int64_t ans = fib(10);  // 55

Utility Functions

Argsort

Returns indices that would sort the array.

template<typename T>
vector<int> argsort(const vector<T> &arr);

Usage Example:

vector<int> arr = {30, 10, 50, 20};
vector<int> indices = argsort(arr);  // {1, 3, 0, 2}
// arr[indices[i]] gives sorted order

Unique Elements

Removes duplicates from a vector.

template<typename T>
void unique(vector<T> &v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

Min/Max Macros

template<typename T>
T min(T a, T b, T c) { return min(a, min(b, c)); }

template<typename T>
T max(T a, T b, T c) { return max(a, max(b, c)); }

template<typename T>
T min(T a, T b, T c, T d) { return min(min(a, b), min(c, d)); }

template<typename T>
T max(T a, T b, T c, T d) { return max(max(a, b), max(c, d)); }

Infinity Values

const int oo = 1e9 + 7;
const int64_t OO = 1e18 + 7;
const double eps = 1e-9;

Direction Arrays

// 4 directions (up, right, down, left)
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

// 8 directions
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

Reverse Operations

template<typename T>
void reverse(vector<T> &v) {
    reverse(v.begin(), v.end());
}

template<typename T>
vector<T> reversed(const vector<T> &v) {
    return vector<T>(v.rbegin(), v.rend());
}

Data Types

Common Type Aliases

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

128-bit Integer

using int128 = __int128;

ostream& operator<<(ostream& os, int128 v) {
    if(v == 0) return os << "0";
    if(v < 0) { os << "-"; v = -v; }
    string s;
    while(v) { s += char('0' + v % 10); v /= 10; }
    reverse(s.begin(), s.end());
    return os << s;
}

N-Dimensional Vector

template<typename T>
vector<T> make_vector(size_t n, T val) {
    return vector<T>(n, val);
}

template<typename T, typename... Args>
auto make_vector(size_t n, Args... args) {
    return vector<decltype(make_vector<T>(args...))>(n, make_vector<T>(args...));
}

Usage Example:

auto dp = make_vector<int>(n, m, k, 0);  // 3D vector initialized to 0

Pragmas

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

Random Utilities

Generate random values for testing and stress testing.

random(from, to)

random_init.cpp

template <typename T> T random(const T from, const T to);

Generates a random value in the range [from, to]. Works with both integers and floating-point types.

random_vector(n, from, to)

random_vector.cpp

template <typename T> vector<T> random_vector(int n, T from, T to);

Generates a vector of n random values in the range [from, to]. Usage Example:

// Generate test case
vector<int> arr = random_vector(1000, 1, 1000000);

// Generate floating-point values
vector<double> values = random_vector(100, 0.0, 1.0);

random_permutation(n, start)

random_permutation.cpp

template <typename T> vector<T> random_permutation(int n, T start = 0);

Generates a random permutation of n elements starting from start. Usage Example:

// Permutation of 0..n-1
vector<int> perm = random_permutation<int>(n);

// Permutation of 1..n
vector<int> perm1 = random_permutation<int>(n, 1);

STD Library Utilities

Useful utilities for working with standard library containers.

find_nearest(set, target)

std_library_find_nearest_set.cpp

template <typename T> T find_nearest(set<T> &st, T target);

Finds the element in the set nearest to the target value. If two elements are equidistant, returns the larger one. Usage Example:

set<int> st = {1, 5, 10, 20};
int nearest = find_nearest(st, 8);  // Returns 10

Rope (GNU Extension)

std_library_rope.cpp

#include <ext/rope>
using namespace __gnu_cxx;

rope<char> r;  // or crope for strings

A rope is a tree-based string data structure supporting efficient operations:

push_back(val) - O(log n)
pop_back() - O(log n)
insert(i, rope) - O(log n) to O(n)
erase(i, n) - O(log n)
substr(i, n) - O(log n)
replace(i, n, rope) - O(log n)
Concatenation with + - O(1)

Usage Example:

crope r("hello");
r.push_back(' ');
r += crope("world");
cout << r << endl;  // "hello world"

Available Utilities

Utility	File	Purpose
Debug	`misc_debug.cpp`	Print debugging
Bits	`misc_bits.cpp`	Bit manipulation
Coordinate Compression	`misc_coordinate_compression.cpp`	Map large values
Y-Combinator	`misc_y_combinator.cpp`	Lambda recursion
Argsort	`misc_argsort.cpp`	Sort indices
Unique	`misc_unique.cpp`	Remove duplicates
Min/Max	`misc_min_max.cpp`	Multi-argument min/max
Infinity	`misc_infinity.cpp`	Infinity constants
Directions	`misc_directions.cpp`	Grid movement
Data Types	`misc_data_types.cpp`	Type aliases
Integer128	`misc_integer128.cpp`	128-bit integers
N-D Vector	`misc_vector_n_d.cpp`	Multi-dimensional vectors
Pairs	`misc_pairs.cpp`	Pair utilities
Loops	`misc_loops.cpp`	Loop macros
Math	`misc_math.cpp`	Math utilities
Date	`misc_date.cpp`	Date calculations
Pragma	`misc_pragma.cpp`	Compiler optimizations
Format Answer	`misc_format_problem_answer.cpp`	Output formatting
Random	`random_init.cpp`	Random value generation
Random Vector	`random_vector.cpp`	Random vector generation
Random Permutation	`random_permutation.cpp`	Random permutations
Find Nearest Set	`std_library_find_nearest_set.cpp`	Find nearest element in set
Rope	`std_library_rope.cpp`	Tree-based string structure

Tips

Use Debug Liberally

Debug statements help catch errors early, automatically disabled on OJ

Bit Operations

GCC built-ins are fast and portable across platforms

Coordinate Compression

Essential for problems with large coordinate ranges

Y-Combinator

Cleaner than separate function definitions for DFS/DP

Data Structures

Advanced data structures

Techniques

Algorithmic techniques

API Reference

Templates

​Overview

​Debugging

​Bit Manipulation

​Basic Bit Operations

​Hamming Distance

​Bit Tricks Cheat Sheet

​Iterate Over Set Bits

​Iterate Over Submasks

​Coordinate Compression

​Y-Combinator

​Utility Functions

​Argsort

​Unique Elements

​Min/Max Macros

​Infinity Values

​Direction Arrays

​Reverse Operations

​Data Types

​Common Type Aliases

​128-bit Integer

​N-Dimensional Vector

​Pragmas

​Random Utilities

​random(from, to)

​random_vector(n, from, to)

​random_permutation(n, start)

​STD Library Utilities

​find_nearest(set, target)

​Rope (GNU Extension)

​Available Utilities

​Tips

Use Debug Liberally

Bit Operations

Coordinate Compression

Y-Combinator

​See Also

Data Structures

Techniques

Build docs developers (and LLMs) love

Overview

Debugging

Bit Manipulation

Basic Bit Operations

Hamming Distance

Bit Tricks Cheat Sheet

Iterate Over Set Bits

Iterate Over Submasks

Coordinate Compression

Y-Combinator

Utility Functions

Argsort

Unique Elements

Min/Max Macros

Infinity Values

Direction Arrays

Reverse Operations

Data Types

Common Type Aliases

128-bit Integer

N-Dimensional Vector

Pragmas

Random Utilities

random(from, to)

random_vector(n, from, to)

random_permutation(n, start)

STD Library Utilities

find_nearest(set, target)

Rope (GNU Extension)

Available Utilities

Tips

See Also