Competitive programming (CP) means solving well-defined algorithmic problems under a time limit, on judges such as Codeforces, CodeChef, AtCoder and LeetCode, and in contests like ICPC. It is also how many Indian companies run their online assessments for placements. Your program reads input, prints output, and must finish within a time limit (often 1–2 seconds) and a memory limit (often 256 MB).
C++ is the most popular CP language for three reasons: it is fast, the STL gives you ready-made, well-tested data structures and algorithms, and you have precise control over types and memory. This final chapter collects everything from the earlier chapters into a practical CP toolkit: the standard template, fast I/O, choosing the right data type, estimating complexity, the STL operations you will use daily, classic code patterns, and the bugs that cost people "Wrong Answer" and "Time Limit Exceeded" verdicts.
How an Online Judge Works
your source ──▶ judge compiles it (e.g. g++ -O2 -std=c++XX)
│
▼
hidden test 1 ──▶ run with time + memory limit ──▶ compare output
hidden test 2 ──▶ ... ──▶ compare output
...
│
▼
Accepted (AC) · Wrong Answer (WA) · Time Limit Exceeded (TLE)
Memory Limit Exceeded (MLE) · Runtime Error (RE) · Compilation Error (CE)A program is accepted only if, for every hidden test, it prints exactly the expected output (usually ignoring trailing whitespace) within the time and memory limits. Passing the sample tests proves very little; you must think about the worst case and the edge cases.
Judges let you pick the C++ version; most offer C++17 and C++20 and many now offer C++23. Choose the newest one available. All programs below were compiled with g++ -std=c++23 -O2 -Wall -Wextra (GCC 15), and the features that need C++17/C++20 are marked.
The Standard CP Template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
vector<ll> a(n);
for (auto& x : a) cin >> x;
ll sum = accumulate(a.begin(), a.end(), 0LL); // 0LL, not 0!
cout << sum << ' ' << *max_element(a.begin(), a.end()) << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
}Input (typed or redirected from a file with ./tpl < input.txt):
3
3
1 2 3
2
1000000000 1000000000
1
-5Output:
6 3
2000000000 1000000000
-5 -5Line by line:
#include <bits/stdc++.h>— a GCC (libstdc++) internal header that includes the entire standard library. It saves typing in contests, but it is not standard C++: it does not exist with MSVC or with Apple's default Clang (which uses libc++), and it slows compilation. Use proper headers in real projects.using namespace std;— normally discouraged (see Namespaces), but accepted in a single-file contest program where you control every name. Avoid naming your own variablescount,distance,maxetc.using ll = long long;— a type alias (C++11) because you will typelong longconstantly.The
solve()function handles one test case;mainreadstand calls itttimes. Declaring variables insidesolve()means each test starts fresh — a common bug is forgetting to reset global arrays between test cases.accumulate(..., 0LL)— the type of the initial value decides the type of the sum (explained below).
Fast Input/Output
Inputs in CP can contain 105–106 numbers. With default settings, cin/cout can be several times slower than necessary, enough to cause TLE. Two lines fix it:
| Line | What it does | Consequence |
|---|---|---|
ios::sync_with_stdio(false); | Stops synchronizing C++ streams with C's stdio, so C++ streams get their own buffers | After this, do not mix cin/cout with scanf/printf; output may appear out of order |
cin.tie(nullptr); | Unties cin from cout; by default cout is flushed before every input operation | In interactive problems you must flush yourself after each query (cout << flush or endl) |
'\n' instead of endl | endl = newline + flush | Printing 106 lines with endl forces 106 flushes; use '\n' |
Reading patterns you will need:
Unknown number of values:
while (cin >> x) { ... }stops at end of input.Whole lines:
getline(cin, s); after acin >> n, skip the leftover newline first withcin >> wsorcin.ignore()(see Input & Output).Printing with spaces but no trailing space:
cout << a[i] << " \n"[i == n - 1];— indexes the string" \n"with abool(0 → space, 1 → newline). Most judges ignore trailing spaces anyway.
Choosing Data Types: Overflow Is the #1 WA
| Type | Range (typical judge, 64-bit) | Safe for |
|---|---|---|
int | −2 147 483 648 to 2 147 483 647 (about ±2.1 × 109) | Values up to 109; never their sums or products |
long long | about ±9.22 × 1018 | Sums of 105 values of 109; products of two numbers below about 3 × 109 |
unsigned long long | 0 to about 1.84 × 1019 | Hashing, bit tricks (arithmetic wraps modulo 264) |
__int128 | about ±1.7 × 1038 | GCC/Clang extension for rare huge products; no cin/cout support |
double | about 15–16 significant digits | Geometry; compare with a tolerance, never with == |
The trap: the type of an expression is decided by its operands, not by the variable you store it in. Compile with the sanitizer to see it:
#include <iostream>
int main() {
int n = 100000;
int bad = n * n; // int * int overflows: undefined behavior
long long wrong = n * n; // still int * int, overflow happens BEFORE conversion
long long right = 1LL * n * n; // promote first, then multiply
std::cout << bad << '\n' << wrong << '\n' << right << '\n';
}g++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined ovf.cpp -o ovf && ./ovfOutput:
ovf.cpp:5:9: runtime error: signed integer overflow: 100000 * 100000 cannot be represented in type 'int'
ovf.cpp:6:25: runtime error: signed integer overflow: 100000 * 100000 cannot be represented in type 'int'
1410065408
1410065408
10000000000Signed overflow is undefined behavior; the value 1410065408 is merely what this run happened to produce (1010 mod 232), and an optimizing compiler is allowed to do anything. long long wrong = n * n; does not help, because the multiplication is done in int before the result is converted. Writing 1LL * n * n makes the first multiplication long long.
The accumulate trap
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<long long> v(3, 2'000'000'000LL);
std::cout << std::accumulate(v.begin(), v.end(), 0) << '\n'; // sum kept in int!
std::cout << std::accumulate(v.begin(), v.end(), 0LL) << '\n'; // correct
}Output:
1705032704
6000000000std::accumulate keeps its running total in the type of the initial value. With 0 (an int) each partial sum is converted back to int and the true answer 6 000 000 000 is lost — silently, with no warning. Always write 0LL (or 0.0 for doubles).
Estimating Complexity Before You Code
A useful rule of thumb: a judge machine performs roughly 108 simple operations per second (it varies by machine and by how cache-friendly the code is). So read the constraints first and let them tell you the algorithm:
| Largest n | Acceptable complexity (about 1 s) | Typical techniques |
|---|---|---|
| n ≤ 10–11 | O(n!) | Try all permutations (next_permutation) |
| n ≤ 20–25 | O(2n · n) | Subsets with bitmasks, bitmask DP |
| n ≤ 500 | O(n3) | Floyd–Warshall, interval DP |
| n ≤ 5 000 | O(n2) | Nested loops, 2-D DP |
| n ≤ 2 × 105 to 106 | O(n log n) | Sorting, binary search, set/map, heaps, segment trees |
| n ≤ 107–108 | O(n) | Prefix sums, two pointers, sieve, linear scans |
| n ≤ 1018 | O(log n) or O(√n) | Binary exponentiation, binary search on the answer, math |
STL operation costs you must know
| Container / algorithm | Operation | Complexity |
|---|---|---|
vector | push_back / index / insert in middle | Amortized O(1) / O(1) / O(n) |
set, map (red-black tree) | insert, erase, find, lower_bound | O(log n) |
unordered_set, unordered_map | insert, find, erase | Average O(1), worst case O(n) |
priority_queue | push, pop / top | O(log n) / O(1) |
deque | push/pop at both ends | O(1) |
sort | whole range | O(n log n) comparisons (guaranteed since C++11) |
lower_bound, upper_bound, binary_search | on a sorted vector | O(log n) |
nth_element | k-th smallest | O(n) on average |
string | s += c / s = s + c / substr(pos, len) | Amortized O(1) / O(n) (copies!) / O(len) |
A classic TLE: calling std::lower_bound(s.begin(), s.end(), x) on a std::set. Set iterators are not random-access, so it takes O(n) steps to move through them. Use the member function s.lower_bound(x), which is O(log n). The same applies to map.
Sorting with Custom Comparators
#include <bits/stdc++.h>
using namespace std;
int main() {
// (name, marks): sort by marks descending, ties by name ascending
vector<pair<string, int>> v{{"Ravi", 85}, {"Asha", 92}, {"Zoya", 85}, {"Dev", 70}, {"Amit", 85}};
sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
if (a.second != b.second) return a.second > b.second; // strict: never true for equal
return a.first < b.first;
});
for (const auto& [name, marks] : v) cout << name << ' ' << marks << '\n';
vector<int> nums{5, 1, 4, 1, 3};
sort(nums.begin(), nums.end(), greater<int>()); // descending
for (int x : nums) cout << x << ' ';
cout << '\n';
}Output:
Asha 92
Amit 85
Ravi 85
Zoya 85
Dev 70
5 4 3 1 1 The comparator answers "should a come before b?" and must define a strict weak ordering. In particular it must return false when the two elements are equal (comp(a, a) must be false). Using <= or >= breaks this rule and is undefined behavior — in practice it can produce wrong order, read past the end of the array, or crash on large inputs. GCC's debug mode catches it:
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v{3, 1, 2, 3, 1};
sort(v.begin(), v.end(), [](int a, int b) { return a <= b; }); // WRONG: not strict
for (int x : v) cout << x << ' ';
cout << '\n';
}g++ -std=c++23 -D_GLIBCXX_DEBUG badcmp.cpp -o badcmp && ./badcmp
Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).Note that std::sort is not stable: elements that compare equal may appear in any order. If the original order of ties matters, use std::stable_sort or add a tie-breaker, as we did with names.
Binary Search: Library and "On the Answer"
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a{1, 3, 3, 3, 7, 9, 12}; // must be sorted
auto lo = lower_bound(a.begin(), a.end(), 3); // first element >= 3
auto hi = upper_bound(a.begin(), a.end(), 3); // first element > 3
cout << "first 3 at index " << (lo - a.begin()) << '\n';
cout << "count of 3 = " << (hi - lo) << '\n';
cout << "has 8? " << binary_search(a.begin(), a.end(), 8) << '\n';
auto it = lower_bound(a.begin(), a.end(), 10);
cout << "smallest >= 10: " << (it != a.end() ? *it : -1) << '\n';
auto it2 = upper_bound(a.begin(), a.end(), 10);
cout << "largest <= 10: " << (it2 != a.begin() ? *prev(it2) : -1) << '\n';
}Output:
first 3 at index 1
count of 3 = 3
has 8? 0
smallest >= 10: 12
largest <= 10: 9 a: 1 3 3 3 7 9 12
index: 0 1 2 3 4 5 6
▲ ▲
lower_bound(3) upper_bound(3) count = 4 - 1 = 3lower_bound returns the first position whose element is not less than the key (≥), and upper_bound the first position whose element is greater (>). Both return end() if no such element exists, so always check before dereferencing.
Binary search on the answer
Many optimization problems ("minimize the maximum ...") have a monotonic yes/no check: if a limit L works, every larger limit works too. Then you can binary search over the answer itself. Example: books with 12, 34, 67 and 90 pages must be split, in order, between 2 students; minimize the maximum pages any student reads.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Can we finish all books with each student reading at most 'limit' pages,
// using at most k students? Books are read in order (contiguous blocks).
bool feasible(const vector<ll>& pages, int k, ll limit) {
int students = 1;
ll current = 0;
for (ll p : pages) {
if (p > limit) return false;
if (current + p > limit) { ++students; current = 0; }
current += p;
}
return students <= k;
}
int main() {
vector<ll> pages{12, 34, 67, 90};
int k = 2;
ll lo = 1, hi = accumulate(pages.begin(), pages.end(), 0LL);
while (lo < hi) { // find the smallest feasible limit
ll mid = lo + (hi - lo) / 2;
if (feasible(pages, k, mid)) hi = mid;
else lo = mid + 1;
}
cout << "minimum maximum pages = " << lo << '\n';
}Output:
minimum maximum pages = 113The best split is [12, 34, 67] = 113 and [90]. Each check is O(n) and there are O(log(sum)) checks, so the total is O(n log(sum)). Note mid = lo + (hi - lo) / 2, which cannot overflow, unlike (lo + hi) / 2 near the top of the range.
Prefix Sums: O(1) Range Queries
For an array a[1..n], the prefix sum array is pre[0] = 0 and pre[i] = pre[i−1] + a[i]. The sum of a[l..r] is then pre[r] − pre[l−1], computed in O(1) after O(n) preprocessing.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<ll> pre(n + 1, 0); // pre[i] = a[1] + ... + a[i]
for (int i = 1; i <= n; ++i) {
ll x;
cin >> x;
pre[i] = pre[i - 1] + x;
}
while (q--) {
int l, r; // 1-based, inclusive
cin >> l >> r;
cout << pre[r] - pre[l - 1] << '\n';
}
}Input:
6 3
4 -2 7 1 5 3
1 3
2 5
4 4Output:
9
11
1Answering q queries by looping over each range would be O(n · q) — up to 1010 operations for n = q = 105. With prefix sums it is O(n + q).
Modular Arithmetic
When the answer is huge, problems ask for it "modulo 109 + 7". This number is prime, and (109 + 6)2 ≈ 1018 still fits in a long long, so you can multiply two reduced values safely before taking % again.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1'000'000'007; // a prime
ll power(ll base, ll exp, ll mod) { // binary exponentiation: O(log exp)
ll result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = result * base % mod;
base = base * base % mod;
exp >>= 1;
}
return result;
}
int main() {
cout << power(2, 10, MOD) << '\n';
cout << power(2, 1'000'000'000'000LL, MOD) << '\n';
ll inv3 = power(3, MOD - 2, MOD); // Fermat: a^(p-2) is the inverse of a mod p
cout << inv3 << ' ' << (3 * inv3) % MOD << '\n';
ll a = 5, b = 8;
cout << ((a - b) % MOD + MOD) % MOD << '\n'; // safe subtraction under modulo
}Output:
1024
959366170
333333336 1
1000000004Binary exponentiation computes ab in O(log b) by squaring: 21012 needs only about 40 iterations.
Modular inverse: for a prime p and a not divisible by p, Fermat's little theorem gives ap−2 ≡ a−1 (mod p). Use it to "divide" under a modulus, e.g. for nCr.
Negative remainders: in C++,
%keeps the sign of the left operand, so(5 - 8) % MODis −3. AddMODand reduce again.Reduce after every operation;
(a * b * c) % MODcan overflow even if each value is reduced.
Bit Manipulation
#include <bits/stdc++.h>
using namespace std;
int main() {
unsigned x = 0b1011'0100; // 180
cout << popcount(x) << ' ' // C++20 <bit>: number of 1 bits
<< __builtin_popcount(x) << ' ' // GCC built-in, same answer
<< countr_zero(x) << ' ' // trailing zeros (C++20)
<< bit_width(x) << '\n'; // floor(log2 x) + 1 (C++20)
int n = 12;
cout << ((n & (n - 1)) == 0 ? "power of 2" : "not a power of 2") << '\n';
cout << "lowest set bit: " << (n & -n) << '\n';
// enumerate all subsets of {a, b, c}
string items = "abc";
int k = items.size();
for (int mask = 0; mask < (1 << k); ++mask) {
cout << '{';
for (int i = 0; i < k; ++i)
if (mask >> i & 1) cout << items[i];
cout << "} ";
}
cout << '\n';
}Output:
4 4 2 8
not a power of 2
lowest set bit: 4
{} {a} {b} {ab} {c} {ac} {bc} {abc} The C++20 header <bit> gives portable std::popcount, std::countr_zero, std::countl_zero, std::bit_width and std::has_single_bit; they accept only unsigned types. The GCC built-ins (__builtin_popcount, __builtin_popcountll for 64-bit, __builtin_ctz, __builtin_clz) are common in older code; note that __builtin_ctz(0) and __builtin_clz(0) are undefined. Also remember that 1 << 40 overflows an int; write 1LL << 40.
Graphs: Dijkstra with a Min-Heap
Graph problems combine several STL pieces: an adjacency list (vector<vector<pair>>), a priority_queue turned into a min-heap with greater<> (see stack, queue & priority_queue), and structured bindings (C++17).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<pair<int, ll>>> adj(n + 1); // adj[u] = {(v, w), ...}
for (int i = 0; i < m; ++i) {
int u, v;
ll w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
const ll INF = LLONG_MAX;
vector<ll> dist(n + 1, INF);
// min-heap of (distance, vertex)
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue; // stale entry, skip
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
for (int v = 1; v <= n; ++v)
cout << (dist[v] == INF ? -1 : dist[v]) << " \n"[v == n];
}Input (5 vertices, 6 undirected weighted edges):
5 6
1 2 4
1 3 1
3 2 2
2 4 5
3 4 8
4 5 3Output (shortest distance from vertex 1 to each vertex):
0 3 1 8 11Instead of a "decrease-key" operation, which priority_queue does not have, we push a new pair and skip outdated ones with if (d != dist[u]) continue;. The complexity is O((n + m) log m). Distances use long long because a path of 105 edges of weight 109 exceeds int.
Hashing Safely: Anti-Hash Tests
unordered_map is O(1) only on average. libstdc++ hashes an integer to itself and uses a predictable sequence of prime bucket counts, so on open-hacking platforms like Codeforces, people craft inputs where every key lands in the same bucket, turning each operation into O(n) and your solution into TLE. Two defenses:
Use
map(guaranteed O(log n)) when its speed is enough.Give
unordered_mapa randomized hash function:
#include <bits/stdc++.h>
using namespace std;
struct SafeHash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t seed =
chrono::steady_clock::now().time_since_epoch().count(); // differs per run
return splitmix64(x + seed);
}
};
int main() {
unordered_map<long long, int, SafeHash> freq;
freq.reserve(1 << 10);
for (long long x : {5LL, 7LL, 5LL, 1'000'000'000'000LL, 5LL}) ++freq[x];
cout << freq[5] << ' ' << freq[7] << ' ' << freq[1'000'000'000'000LL] << '\n';
}Output:
3 1 1splitmix64 scrambles the bits thoroughly, and adding a seed taken from the clock means the hacker cannot predict the bucket of a key. reserve pre-allocates buckets so the table does not repeatedly rehash as it grows.
Debugging Like a Pro
| Tool / flag | What it catches |
|---|---|
-Wall -Wextra -Wshadow -Wconversion | Unused variables, shadowed names, lossy conversions such as int x = someLongLong; |
-fsanitize=address,undefined | Out-of-bounds access, use after free, signed overflow, invalid shifts |
-D_GLIBCXX_DEBUG | libstdc++ debug mode: out-of-range vector indexing, invalid iterators, bad comparators |
cerr for debug prints | Most judges ignore standard error, but leftover prints still cost time — remove them before submitting |
| Brute-force checker | Write a slow, obviously-correct solution and compare outputs on many small random tests |
Compile locally with sanitizers and debug mode, but submit without them: they make the program several times slower.
Common Mistakes
intwherelong longis needed — sums, products, distances, answers that "can be large".accumulate(v.begin(), v.end(), 0)on large values — use0LL.endlin a loop printing 106 lines — flushes every time; use'\n'.Mixing
scanf/printfwithcin/coutaftersync_with_stdio(false).v.size() - 1whenvis empty —size()is unsigned, so the result wraps to a huge number. Cast tointfirst or check emptiness.Comparator with
<=— undefined behavior insort,setandmap.std::lower_boundon aset/map— O(n); use the member function.Large local arrays like
int a[1000000];inside a function can overflow the stack (limits differ between judges); make them global,static, or avector. Global arrays are also zero-initialized automatically.Not resetting data between test cases — global arrays and containers keep values from the previous test.
memset(a, 1, sizeof a)to fill anintarray with 1 —memsetsets bytes, giving 16843009; only 0 and −1 work this way. Usefillorvector's constructor.Very deep recursion (DFS on a 106-node path) — may overflow the stack; use an explicit stack if the judge's stack is small.
Comparing
doublewith==— usefabs(a - b) < 1e-9.
Interview / GATE-Style Questions
Q1. What do ios::sync_with_stdio(false) and cin.tie(nullptr) do, and when can they cause bugs?
The first disables synchronization between C++ streams and C stdio, letting cin/cout use their own fast buffers; mixing them with scanf/printf afterwards can reorder input or output. The second stops cout from being flushed before each read from cin; in interactive problems you must then flush explicitly after every query, or the judge never sees it.
Q2. int n = 100000; long long x = n * n; — what is x?
The behavior is undefined: n * n is computed in int and overflows before the conversion to long long. On typical machines you see 1410065408, but nothing is guaranteed. Write 1LL * n * n or make n a long long.
Q3. n ≤ 2 × 105 and the time limit is 1 second. Is an O(n2) algorithm acceptable?
No. 4 × 1010 operations is hundreds of times more than about 108 per second. You need O(n log n) or O(n).
Q4. Why should a comparator passed to std::sort never use <=?
std::sort requires a strict weak ordering, which includes irreflexivity: comp(a, a) must be false. With <=, equal elements compare "less" both ways, which violates the precondition. The result is undefined behavior: wrong order, out-of-bounds reads or a crash.
Q5. How do you count occurrences of x in a sorted vector in O(log n)?
upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x), which is the distance between the first element > x and the first element ≥ x.
Q6. Why is 109 + 7 such a popular modulus?
It is prime, so every nonzero value has a modular inverse (via Fermat's little theorem), and it is just under 230, so the sum of two reduced values fits in int and the product of two reduced values (below about 1018) fits in a 64-bit long long.
Q7. Can unordered_map be slower than map?
Yes. Its average cost is O(1), but with many collisions (for example, deliberately crafted anti-hash inputs) operations degrade to O(n), and rehashing plus poor cache behavior adds constant factors. map guarantees O(log n). A randomized custom hash and reserve make unordered_map safe and fast.
Summary
Start from a template:
solve()per test case, fast I/O (sync_with_stdio(false),cin.tie(nullptr)), and'\n'instead ofendl.<bits/stdc++.h>andusing namespace std;are contest conveniences, not good practice in real projects.Use
long longfor sums, products and answers; promote before multiplying (1LL * a * b); startaccumulatewith0LL.Read the constraints and estimate complexity using about 108 simple operations per second.
Know STL costs:
set/mapO(log n), unordered containers O(1) average but O(n) worst,sortO(n log n); use memberlower_boundon sets and maps.Core patterns: custom comparators (strict!),
lower_bound/upper_bound, binary search on the answer, prefix sums, modular exponentiation and inverse, bitmasks, Dijkstra with a min-heap.Debug locally with
-Wall -Wextra,-fsanitize=address,undefinedand-D_GLIBCXX_DEBUG; submit without them.