SyntaxPilot
Courses/Competitive Programming/Lesson 2
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 2 of 90

C++ setup for contests: template, fast I/O, bits/stdc++

queued

These are the notes for Competitive Programming episode 2. You will build the C++ template, the ready-made starting file you copy for every contest problem, and understand every line of it: #include <bits/stdc++.h>, using ll = long long, multiple test cases with solve() and while (t--), and the two fast I/O lines. You will also measure, live, how much faster input gets with fast I/O, why endl is slow, and a printing-order trap that appears once fast I/O is on. Every example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler). Timings are from one run on the recording machine; your numbers will differ, but the ratios hold.

The problem: a compilation error at minute 7

An easy contest problem needs a list of numbers (vector, a resizable array) and sorting (sort). Typing fast, you start with the include you always use:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    cout << a[0] << " " << a[n - 1] << endl;
    return 0;
}

Compilation Error:

main.cpp:7:5: error: 'vector' was not declared in this scope
main.cpp:9:5: error: 'sort' was not declared in this scope; did you mean 'short'?

Each part of the C++ standard library lives in its own header (<vector>, <algorithm>, <string>, <map> ...), and we forgot two of them.

The fix: one header for everything

#include <bits/stdc++.h>

With input 4 / 7 2 9 4 the program now prints 2 9. bits/stdc++.h includes the entire standard library at once.

Separate headers bits/stdc++.h
Fetch each tool from the shelf Carry the whole toolbox
Fast to compile Slightly slower to compile (fine in contests)
Standard C++, works everywhere GCC only: not in MSVC (Visual Studio), not in Apple clang on a Mac by default
Use in real projects Use in contests (judges use GCC)

Multiple test cases

Most Codeforces-style problems put many small tests in one input file.

Problem B · Score Spread (written for this course). The input has t test cases. Each has n and then n scores. For each test case, print the largest score minus the smallest score.

Constraints: 1 ≤ t ≤ 10^4, 1 ≤ n ≤ 2·10^5, 1 ≤ a[i] ≤ 10^9, and the sum of n over all test cases is at most 2·10^5.

Sample input Sample output
3
3
5 1 4
1
7
4
10 10 2 8
4
0
8

What "sum of n over all test cases ≤ 2·10^5" means: t × max n would be 2 · 10^9, but the whole file contains at most 2 · 10^5 scores in total, however they are split. So an O(n) or O(n log n) solution per test is fast overall. Without this line, you would have to assume the worst case for every test.

The structure is like a teacher checking a stack of answer sheets:

Exam checking Code
The top sheet says how many papers cin >> t;
Same steps for each paper; marks never leak between students void solve() with its own fresh variables
Repeat until the stack is empty while (t--) solve();

t-- tests the current value of t, then decreases it, so the loop body runs exactly t times (and t ends at -1).

The template, line by line

#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 mx = *max_element(a.begin(), a.end());
    ll mn = *min_element(a.begin(), a.end());
    cout << mx - mn << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Output on the sample: 4, 0, 8.

Line Why it is there
#include <bits/stdc++.h> The whole standard library
using namespace std; Write vector instead of std::vector
using ll = long long; A short name (a type alias) for a type you type constantly
void solve() Handles exactly one test case; only this part changes per problem
for (auto &x : a) cin >> x; x is a reference to each element (the element itself, not a copy), so cin fills the real vector
*max_element(...) max_element returns an iterator (a position in the container); * reads the value there
'\n' A newline without flushing (see below)
ios::sync_with_stdio(false); + cin.tie(nullptr); Fast I/O
while (t--) solve(); Run solve once per test case

Fast input, measured

Some problems have millions of numbers in the input. By default cin:

  1. stays synchronised with C's scanf/printf (they share one buffer so you can mix them safely), and
  2. is tied to cout: before every read it flushes cout (pushes any waiting output to the screen).

Contest programs need neither. The measuring program writes 2,000,000 numbers to a file, points cin at it with freopen, and times only the reading with the chrono stopwatch:

#include <bits/stdc++.h>
using namespace std;

int main() {
    // (the two fast I/O lines go here in the second run)
    {
        ofstream f("in.txt");
        for (int i = 0; i < 2000000; i++) f << i << ' ';
    }
    if (!freopen("in.txt", "r", stdin)) return 1;
    auto start = chrono::steady_clock::now();
    long long sum = 0, x;
    while (cin >> x) sum += x;
    auto end = chrono::steady_clock::now();
    cout << "sum = " << sum << endl;
    cout << "read in " << (end - start) / 1ms << " ms" << endl;
    return 0;
}
Version Output (one run)
Plain cin sum = 1999999000000 / read in 450 ms
With ios::sync_with_stdio(false); cin.tie(nullptr); sum = 1999999000000 / read in 90 ms

About 5× faster, with no change to the algorithm. A buffer is a waiting area where text collects before it moves in one big chunk; turning sync off gives cin/cout their own fast buffer.

Rules for the two lines:

  • Put them at the very top of main, before any input or output.
  • After sync_with_stdio(false), never mix cin/cout with scanf/printf/puts.
  • cin.tie(nullptr) is unsafe only for interactive problems (where the judge answers your output): there you must flush after each query (cout << ... << endl or cout.flush()).

endl vs '\n', measured

endl prints a newline and flushes. '\n' only prints the newline; the buffer is sent in big chunks.

#include <bits/stdc++.h>
using namespace std;

int main() {
    auto t0 = chrono::steady_clock::now();
    ofstream a("a.txt");
    for (int i = 0; i < 1000000; i++) a << i << endl;
    auto t1 = chrono::steady_clock::now();
    ofstream b("b.txt");
    for (int i = 0; i < 1000000; i++) b << i << '\n';
    auto t2 = chrono::steady_clock::now();
    cout << "endl: " << (t1 - t0) / 1ms << " ms" << endl;
    cout << "\\n:   " << (t2 - t1) / 1ms << " ms" << endl;
    return 0;
}

One run printed endl: 398 ms and \n: 33 ms, about 10× slower for the same text. Like walking to the post office after every letter instead of filling the bag first. Use '\n' in every loop.

The printf trap

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << "1. cout\n";
    printf("2. printf\n");
    cout << "3. cout\n";
    return 0;
}

Output:

1. cout
3. cout
2. printf

With sync off, cout and printf have separate buffers, and each empties whenever it likes. On a judge this is a Wrong Answer. Pick one system and stick to it.

Common mistakes (and the real messages)

Mistake What you see Why Fix
Only #include <iostream>, then vector/sort error: 'vector' was not declared in this scope Each tool needs its header #include <bits/stdc++.h>
Sync off, then printf Lines out of order (no error) Two separate buffers Use only cin/cout
endl in a loop of 10^6 lines Time limit exceeded endl flushes every line '\n'
A global vector reused across tests Wrong answer on test 2 Old values leak into the next test Declare inside solve()
Fast I/O lines after the first cin Little or no speed-up They must come before any I/O First lines of main
bits/stdc++.h on a Mac fatal error: 'bits/stdc++.h' file not found Apple clang doesn't ship it Install GCC, or use the online compiler

Score Spread: brute force vs optimal

Approach Time Memory
Sort each test, take last − first O(n log n) per test O(n)
One pass with max_element / min_element O(n) per test, O(sum of n) overall O(n) (O(1) if you don't store the array)

Solution in C++, Java and Python

C++ — the template above.

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int t = nextInt(in);
        StringBuilder out = new StringBuilder();
        while (t-- > 0) {
            int n = nextInt(in);
            long mx = Long.MIN_VALUE, mn = Long.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                long x = nextInt(in);
                mx = Math.max(mx, x);
                mn = Math.min(mn, x);
            }
            out.append(mx - mn).append('\n');
        }
        System.out.print(out);
    }

    static int nextInt(DataInputStream in) throws IOException {
        int ret = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { ret = ret * 10 + (b - '0'); b = in.read(); }
        return ret;
    }
}

(Java's equivalent of fast I/O: read bytes through a buffer, and collect output in a StringBuilder instead of printing line by line. This nextInt handles the non-negative numbers of this problem.)

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0]); pos = 1
    out = []
    for _ in range(t):
        n = int(data[pos]); pos += 1
        a = data[pos:pos + n]; pos += n
        nums = list(map(int, a))
        out.append(max(nums) - min(nums))
    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

(Python's fast I/O: read the whole input at once with sys.stdin.buffer.read() and write once at the end.)

Mini project: your personal template file

Create template.cpp with the code above, but with an empty solve():

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;   // delete this line when a problem has a single test
    while (t--) solve();
    return 0;
}

Copy it at the start of every problem. Many contestants also add const ll MOD = 1e9 + 7; (you will need it from episode 21). Keep the template short: every line should have a reason.

Practice

  1. Rewrite Chai Batches from episode 1 using the template (single test: set t = 1 and remove cin >> t).

    Solution ```cpp void solve() { ll n, k; cin >> n >> k; ll sum = 0; for (int i = 0; i < n; i++) { ll a; cin >> a; sum += a; } cout << (sum + k - 1) / k << '\n'; } ```

  2. Score Spread, but print the second largest distinct score, or -1 if there isn't one.

    Solution Sort, remove duplicates (`a.erase(unique(a.begin(), a.end()), a.end());`), then print `a[a.size() - 2]` if `a.size() >= 2`, else `-1`.

  3. Time endl vs '\n' for 10^5 and 10^7 lines. Is the ratio roughly constant?

    Solution Yes: both grow linearly, and `endl` stays several times slower because every line costs a flush (a system call).

Quick quiz

int t = 3;
while (t--) solve();

How many times does solve() run, and what is t afterwards?

A) 3, t = 0 B) 3, t = -1 C) 2, t = 0 D) 4, t = -1

Answer

B. The loop tests 3, 2, 1 (true, so solve runs 3 times), then tests 0 (false) and stops, but that last test still decreases t to -1.

Interview questions

  1. What does ios::sync_with_stdio(false) do, and what is the risk? (Unsyncs C++ streams from C stdio for speed; mixing printf/scanf with cout/cin then gives out-of-order or wrong I/O.)
  2. Why is endl slower than '\n'? (It flushes the stream every time.)
  3. Why shouldn't you use bits/stdc++.h in production code? (Not standard, GCC only, slower compiles, hides real dependencies.)
  4. When must you flush output explicitly? (Interactive problems, and before a program might crash if you need the output.)

Glossary

Term Meaning Example
Template A ready-made starting file you copy for every problem The file above
Header A file that declares a part of the library <vector>, <algorithm>
bits/stdc++.h GCC's header that includes the whole standard library #include <bits/stdc++.h>
vector A resizable array vector<ll> a(n);
Type alias A new name for an existing type using ll = long long;
Test case One independent problem instance inside the input one block of Score Spread
Sum of n constraint A bound on the total size of all test cases together sum of n ≤ 2·10^5
solve() The function that handles one test case void solve() { ... }
Reference (&) Another name for the same variable, not a copy for (auto &x : a)
Iterator A position inside a container a.begin(), max_element(...)
Stream A flow of characters in or out of a program cin, cout, cerr
Buffer A waiting area where output collects before being sent the cout buffer
Flush Push everything waiting in the buffer out now endl, cout.flush()
Fast I/O Turning off sync and tie so cin/cout run at full speed the two lines in main
freopen Redirects stdin/stdout to a file freopen("in.txt", "r", stdin)
chrono The C++ time library, used here as a stopwatch chrono::steady_clock::now()
Interactive problem A problem where the judge replies to your output guess-the-number problems

Summary

  • #include <bits/stdc++.h> brings the whole standard library (GCC only; fine for contests).
  • Multiple test cases: cin >> t; while (t--) solve(); with all per-test variables inside solve().
  • "Sum of n over all test cases" bounds the total work.
  • ios::sync_with_stdio(false); cin.tie(nullptr); makes input several times faster. Put them first in main.
  • Use '\n', not endl, in loops.
  • With sync off, never mix printf/scanf with cout/cin.

Next episode: reading constraints, from n to the complexity you need.