The contest template and fast I/O

Every solution in this part starts the same way, and it is worth knowing what those lines actually buy before you copy them for the next forty chapters.

#include <bits/stdc++.h>          // everything, on GCC and Clang
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    …
}

Two of those four lines are performance, one is convenience, and one is a habit this book has spent nine parts arguing against. All four deserve a reason.

What sync_with_stdio(false) is worth

By default, C++ streams are kept synchronised with C’s stdio — every cin >> is coordinated with anything that might have used scanf, so that mixing them works. Almost nobody mixes them, and the coordination is not free.

One million integers, read three ways, best of three runs at -O2:

Nearly four times, for two lines. And note the third row: unsynchronised cin is faster than scanf here. The folklore that scanf is the fast option is out of date — it was true when the streams were slow, and what is actually slow is the synchronisation.

cin.tie(nullptr) is the second half. By default cin is tied to cout, meaning every read flushes pending output first — which is what makes an interactive prompt appear before the program waits. A contest program has nobody to prompt, and the flush per read is pure cost.

'\n' versus std::endl

std::endl writes a newline and flushes the stream. Flushing means a system call. Doing that once per line of a large output is the other common way to exceed a time limit.

300,000 lines of output:

Ten times, writing to a file. The stream flushes when it is destroyed at the end of main, so nothing is lost by not flushing yourself.

Use '\n'. Reach for std::endl only when you genuinely need the output to appear now — interactive problems, and debugging a program that crashes.

The input shapes

Four cover almost everything.

A count, then that many values. The common case.

int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;

Several test cases in one file. The first number is how many follow.

int tests;
cin >> tests;
while (tests--) {
    // read and solve one case
}

Values until the end of input, with no count given.

#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    long long value;
    long long total = 0;
    int count = 0;

    while (std::cin >> value) {      // false when extraction fails or EOF
        total += value;
        ++count;
    }

    std::cout << count << " values, sum " << total << '\n';
}

With no input at all — which is what this page gives it — that prints 0 values, sum 0, because the loop body never runs. That is the correct behaviour for an empty file, and it costs nothing to get right.

Lines, rather than whitespace-separated tokens. This is the one with a trap.

#include <iostream>
#include <sstream>
#include <string>

int main() {
    // Standing in for an input file containing "3\nhello world\n".
    std::istringstream input("3\nhello world\n");

    int n;
    input >> n;                       // reads 3, leaves the newline behind

    std::string first;
    std::getline(input, first);       // reads the rest of the line: nothing
    std::cout << "n = " << n << ", first getline: [" << first
              << "] length " << first.size() << '\n';

    std::string second;
    std::getline(input, second);      // now the line you wanted
    std::cout << "second getline: [" << second << "]\n";
}

cin >> n stops at the newline and leaves it in the buffer. The next getline reads from there to the end of that line, which is an empty string. The fix is to consume the rest of the line first:

cin >> n;
cin.ignore(numeric_limits<streamsize>::max(), '\n');   // discard to end of line
getline(cin, line);

or, more simply, use >> for everything when the input has no embedded spaces, and getline for everything when it does. Mixing them is what causes this.

#include <bits/stdc++.h>

A GCC and Clang implementation detail that includes the entire standard library in one line. It is not standard C++ and does not exist on MSVC.

It is right for a contest and wrong for everything else. In a contest you are optimising for the twenty seconds it takes to remember whether std::accumulate is in <numeric> or <algorithm>, and nobody will ever compile your file again. Chapter 7.6 measured what it costs — seven unused standard headers took an empty program from 35 ms to over a second to compile, and bits/stdc++.h is all of them — which matters enormously in a project and not at all for a file compiled once.

Every sample in this part includes what it uses, because they are teaching material and a reader should be able to see where a name comes from. Your contest template should use bits/stdc++.h. Both statements are true.

using namespace std;

Chapter 4.9 argued against this, and that argument stands for any code that lives longer than a submission: it drags every standard name into the global namespace, where it can collide with yours, and the collisions are found at the worst moment.

In a contest file the tradeoff genuinely reverses. Nothing else is in the file, nobody links against it, and sort(all(a)) beats std::sort(a.begin(), a.end()) when you are typing against a clock.

The one thing to know is which names it captures, because these bite:

That last row is the famous one: int y1; fails to compile on GCC with a message about a conflicting declaration, because <cmath> puts a function called y1 in the global namespace. Chapter 5.5’s authoring notes hit the same thing with gamma. Name your variables y_1, or anything else.

A template worth using

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

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests = 1;
    // cin >> tests;              // uncomment when the input has a case count

    while (tests--) {
        int n;
        cin >> n;

        vector<ll> a(n);
        for (ll& x : a) cin >> x;

        // solve

        cout << "\n";
    }
}

Short on purpose. Templates that arrive with two hundred lines of macros, a debug printer and a segment tree cost more than they save: you spend the first minute scrolling past code you are not using, and the macros make the compiler’s error messages worse at the moment you most need them.

The two things worth having beyond the above are using ll = long long;, because you will type it constantly, and the multi-test-case loop, because switching a solution to it under time pressure is exactly when mistakes happen.

Check yourself

Practice