C++

Fast I/O, Contest Templates and Stress Testing

Read and write large inputs without wasting time, keep a small modern C++ template, and catch wrong answers before the judge does with a stress-test harness.

When the algorithm is right and the verdict is not

Two things go wrong with solutions whose algorithm is correct and fast enough. The first is input and output. A problem with 10^6 numbers in the input and 10^6 lines in the output spends a real part of its time limit just moving characters, and the default settings of C++ streams, plus one habit (std::endl), can make that part several times slower than necessary. The second is a bug that the sample does not reveal: an off-by-one, a wrong initial value, a case nobody thought of. The judge says "wrong answer on test 14" and shows you nothing.

This lesson fixes both. It covers the solve(std::istream&, std::ostream&) structure used throughout the course, the two lines of stream setup that matter and why, a fast integer reader built on std::from_chars, a small template of modern C++ that is worth keeping, and a stress-test harness that finds the input your solution gets wrong. It ends with the runtime errors you will meet most often and what each one looks like.

It builds on Complexity in Practice, where the brute-force-versus-fast comparison first appeared, and on input and output with streams from I/O and Formatting.

One function that reads, one that writes

Every program in this course has the same shape. The solution lives in solve, which takes an input stream and an output stream. main decides where they come from. In the browser playground there is no keyboard input, so main wraps the sample in a std::istringstream. On a judge, main calls solve(std::cin, std::cout) and nothing else changes.

This also makes testing easy: you can call solve on a string and capture what it writes in a std::ostringstream, which the harness later in this lesson does.

Shift log. A workshop logs shifts as lines of the form name minutes, with no count at the start. Print each worker's total, in alphabetical order. Since the number of lines is not given, the program reads until the input runs out.

ana 90
li 45
ana 30
sam 120
li 15
main.cppc++23
#include <iostream>
#include <map>
#include <sstream>
#include <string>

void solve(std::istream& in, std::ostream& out) {
    std::map<std::string, long long> total;  // sorted by name
    std::string name;
    long long minutes;
    while (in >> name >> minutes) total[name] += minutes;  // stops at end of input
    for (const auto& [who, sum] : total) out << who << ' ' << sum << '\n';
}

int main() {
    std::istringstream sample("ana 90\nli 45\nana 30\nsam 120\nli 15\n");
    solve(sample, std::cout);  // on a judge: solve(std::cin, std::cout)
}
Output

Press Run to compile and run this example.

ana 120
li 60
sam 120

in >> name >> minutes returns the stream, and a stream converts to false once a read fails, which happens at the end of the input. The same loop also stops at malformed input, so if a problem promises a count, read it and use it instead.

The two lines of stream setup, and what they do

Many C++ contest solutions start with these two lines:

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

They are worth understanding rather than copying.

sync_with_stdio(false). By default the eight standard C++ streams are synchronized with the C streams (stdin, stdout and so on), so that std::cout << x and printf can be mixed freely and appear in order. In practice, as cppreference puts it, this means the synchronized C++ streams are unbuffered and every operation is passed straight to the C stream. Turning synchronization off lets the C++ streams buffer independently, which can be considerably faster. The price: after this call you must not mix std::cout with printf or std::cin with scanf, because the two now have separate buffers and their output can come out in the wrong order. Call it before any input or output; if I/O has already happened, the effect is implementation-defined.

std::cin.tie(nullptr). By default std::cin is tied to std::cout: before each input operation on std::cin, std::cout is flushed, so a prompt appears before the program waits for an answer. Useful for an interactive program; useless when the whole input is a file. Untying removes those flushes.

The third habit is to end lines with '\n' instead of std::endl. std::endl writes a newline and flushes the stream, which forces the buffered text out to the operating system on every line. We can count those flushes. A stream buffer's sync() member is what a flush calls in the end, so a buffer that counts its sync() calls shows exactly how many flushes each style causes.

main.cppc++23
#include <ostream>
#include <print>
#include <sstream>

// A string buffer that counts how often the stream asks it to flush.
struct CountingBuf : std::stringbuf {
    int flushes = 0;
    int sync() override { ++flushes; return std::stringbuf::sync(); }
};

int main() {
    CountingBuf withEndl, withNewline;
    std::ostream a(&withEndl), b(&withNewline);
    for (int i = 0; i < 1000; ++i) {
        a << i << std::endl;  // newline + flush
        b << i << '\n';       // newline only
    }
    b.flush();  // one flush at the end is all that is needed
    std::println("std::endl: {} flushes, {} characters", withEndl.flushes,
                 withEndl.str().size());
    std::println("'\\n':      {} flushes, {} characters", withNewline.flushes,
                 withNewline.str().size());
}
Output

Press Run to compile and run this example.

std::endl: 1000 flushes, 3890 characters
'\n':      1 flushes, 3890 characters

Same output, a thousand times more flushes. Writing into a string is cheap even when flushed, so this program does not get slower; on a judge, where each flush of std::cout can mean a call into the operating system, that is where the time goes. The output is flushed anyway when the program exits normally, so you never need std::endl for correctness in a batch problem.

One exception matters: interactive problems, where your program asks the judge a question and reads the reply. There you must flush after each question (std::cout << std::flush, or std::endl on that line), otherwise the judge waits for a question that is sitting in your buffer, and you get a time limit or "idleness" verdict.

A faster reader with `std::from_chars`

For most problems the two setup lines are enough. When the input has many millions of numbers, a hand-written reader helps: read the whole input into one std::string, then parse it in place. std::from_chars (C++17, header <charconv>) is the right tool for the parsing. It does not use the locale, does not allocate and does not throw, and it reports where it stopped.

Two details of its contract shape the reader. It does not skip leading whitespace, so the reader skips spaces and newlines itself. And it accepts a leading minus sign but not a plus sign. The program shows both, then reads a list of numbers and builds the whole answer in one string with std::format_to before writing it once.

main.cppc++23
#include <cctype>
#include <charconv>
#include <format>
#include <iostream>
#include <iterator>
#include <print>
#include <sstream>
#include <string>
#include <vector>

using ll = long long;

struct Scanner {
    std::string data;
    std::size_t pos = 0;
    explicit Scanner(std::istream& in) : data(std::istreambuf_iterator<char>(in), {}) {}

    bool next(ll& value) {  // false at end of input or on a malformed number
        while (pos < data.size() && std::isspace(static_cast<unsigned char>(data[pos])))
            ++pos;  // from_chars does not skip whitespace
        const char* first = data.data() + pos;
        auto [end, ec] = std::from_chars(first, data.data() + data.size(), value);
        if (ec != std::errc{}) return false;
        pos = end - data.data();
        return true;
    }
};

void solve(std::istream& in, std::ostream& out) {  // print each number doubled
    Scanner scan(in);
    std::string answer;
    for (ll x; scan.next(x);) std::format_to(std::back_inserter(answer), "{}\n", 2 * x);
    out << answer;  // one write for the whole output
}

int main() {
    ll v = 0;
    std::string text = " 42";
    auto r1 = std::from_chars(text.data(), text.data() + text.size(), v);
    std::println("\" 42\": ok = {}", r1.ec == std::errc{});
    text = "+42";
    auto r2 = std::from_chars(text.data(), text.data() + text.size(), v);
    std::println("\"+42\": ok = {}", r2.ec == std::errc{});

    std::istringstream sample("5\n-17 300000000000\n  8\n");
    solve(sample, std::cout);
}
Output

Press Run to compile and run this example.

" 42": ok = false
"+42": ok = false
10
-34
600000000000
16

Reading everything at once costs memory equal to the input size, which is fine for inputs of tens of megabytes. Reach for it when the input has several million numbers or more. Below that, std::cin >> x with the two setup lines is simpler and fast enough.

A small template, and what to leave out

A contest template is the code you paste at the start of every solution. Long templates full of macros were common once; most of what they offered is now in the language. Here is a restrained one: the headers it uses, two aliases, the course's kInf, the stream setup in main, and solve. It solves a small original problem to show the modern idioms worth knowing.

Packing choices. You have n <= 20 boxes with given weights and a bag that holds at most W. How many subsets of boxes fit? Also print the boxes from heaviest to lightest, with their original positions. With n <= 20 the complexity table says O(2^n) is fine, so a recursion that decides "take or skip" for each box is the intended solution.

5 10
4 7 1 3 6
main.cppc++23
#include <algorithm>
#include <bit>
#include <iostream>
#include <limits>
#include <ranges>
#include <sstream>
#include <vector>

using ll = long long;
constexpr ll kInf = std::numeric_limits<ll>::max() / 4;  // safe to add twice

void solve(std::istream& in, std::ostream& out) {
    int n;
    ll limit;
    in >> n >> limit;
    std::vector<ll> w(n);
    for (ll& x : w) in >> x;

    // Recursive lambda with an explicit object parameter (C++23 "deducing this").
    auto count = [&](this auto&& self, int i, ll used) -> ll {
        if (used > limit) return 0;
        if (i == n) return 1;
        return self(i + 1, used) + self(i + 1, used + w[i]);  // skip or take box i
    };
    out << count(0, 0) << " subsets fit\n";

    std::vector<std::pair<ll, int>> boxes;  // (weight, position)
    for (int i : std::views::iota(0, n)) boxes.push_back({w[i], i + 1});
    std::ranges::sort(boxes, std::greater<>{});
    for (const auto& [weight, position] : boxes)
        out << "box " << position << " weighs " << weight << '\n';

    out << "a power-of-two size for " << n << " leaves: " << std::bit_ceil(unsigned(n))
        << ", kInf + kInf still fits: " << (kInf + kInf > kInf) << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::istringstream sample("5 10\n4 7 1 3 6\n");
    solve(sample, std::cout);  // on a judge: solve(std::cin, std::cout)
}
Output

Press Run to compile and run this example.

16 subsets fit
box 2 weighs 7
box 5 weighs 6
box 1 weighs 4
box 4 weighs 3
box 3 weighs 1
a power-of-two size for 5 leaves: 8, kInf + kInf still fits: 1

What each idiom buys you:

  • Structured bindings (const auto& [weight, position]) name the parts of a pair instead of .first and .second.
  • std::ranges::sort takes the container directly; std::greater<>{} sorts descending.
  • std::views::iota(0, n) is a range of indices, handy when you need the index and want a range-based loop.
  • Deducing this (C++23) lets a lambda call itself through its first parameter, self. Before C++23 the usual workarounds were std::function (slower, an indirect call) or passing the lambda to itself by hand.
  • std::bit_ceil (C++20, <bit>) gives the smallest power of two not below x: the size you need for an iterative segment tree in lesson 9.
  • kInf = max / 4 is a large value that you can add to itself without overflow, which shortest-path code does all the time.

What to leave out, and why:

  • #include <bits/stdc++.h> is a GCC internal header, not standard C++. It fails on compilers that do not ship it and pulls in the entire library, which slows compilation.
  • using namespace std; in a header you share pulls every standard name into every file that includes it. In a single-file solution it is a matter of taste; this course writes std:: to keep names unambiguous.
  • Macros for loops and constants (#define rep(i, n) ..., #define INF 1e18) have no types and no scope. #define INF 1e18 is a double, not an integer. And a function-like macro pastes text, which goes wrong in ways that do not look like errors:
main.cppc++23
#include <print>

#define SQUARE(x) x * x  // text substitution, not a function

constexpr long long square(long long x) { return x * x; }

int main() {
    int a = 3;
    std::println("SQUARE(a + 1) = {}", SQUARE(a + 1));  // expands to a + 1 * a + 1
    std::println("square(a + 1) = {}", square(a + 1));
}
Output

Press Run to compile and run this example.

SQUARE(a + 1) = 7
square(a + 1) = 16

A constexpr function is just as fast, has a type, and computes what it says.

A stress-test harness that finds the bad input

The previous lesson compared a fast solution with a brute force on random inputs. Here is the same idea as a reusable harness with three parts: a generator of small random inputs, a brute force that is obviously correct, and the solution under test. When they disagree, the harness does not stop at the first counterexample. It shrinks it: it tries deleting one element at a time and keeps any deletion after which the two still disagree. The result is a minimal failing input that you can check by hand.

Best pair product. Given n integers (2 <= n <= 2*10^5, each between -10^9 and 10^9), print the largest product of two of them at different positions. The product reaches 10^18, which fits in long long (whose maximum is about 9.22*10^18), so long long is enough.

The tempting fast solution sorts and multiplies the two largest values. Let us see what the harness makes of it.

main.cppc++23
#include <algorithm>
#include <cstdint>
#include <functional>
#include <print>
#include <vector>

using ll = long long;
using Input = std::vector<ll>;

struct Lcg {
    std::uint64_t s;
    std::uint32_t next() {
        s = s * 6364136223846793005ULL + 1442695040888963407ULL;
        return std::uint32_t(s >> 33);
    }
    int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};

ll brute(const Input& a) {  // every pair, straight from the statement
    ll best = a[0] * a[1];
    for (std::size_t i = 0; i < a.size(); ++i)
        for (std::size_t j = i + 1; j < a.size(); ++j) best = std::max(best, a[i] * a[j]);
    return best;
}

ll twoLargest(Input a) {  // the tempting version
    std::ranges::sort(a);
    return a[a.size() - 1] * a[a.size() - 2];
}

ll largestOrSmallest(Input a) {  // two big positives or two big negatives
    std::ranges::sort(a);
    return std::max(a[a.size() - 1] * a[a.size() - 2], a[0] * a[1]);
}

void show(const char* label, const Input& a) {
    std::print("{} [", label);
    for (ll x : a) std::print(" {}", x);
    std::println(" ]");
}

using Solver = std::function<ll(const Input&)>;

void stress(const char* name, const Solver& fast, int tests) {
    Lcg rng{12345};
    for (int t = 1; t <= tests; ++t) {
        Input a(rng.range(2, 8));
        for (ll& x : a) x = rng.range(-9, 9);
        if (brute(a) == fast(a)) continue;
        std::println("{}: wrong on test {}", name, t);
        show("  found: ", a);
        // Shrink: drop elements while the input stays valid and still fails.
        for (std::size_t i = 0; i < a.size() && a.size() > 2;) {
            Input smaller = a;
            smaller.erase(smaller.begin() + i);
            if (brute(smaller) != fast(smaller)) a = smaller; else ++i;
        }
        show("  shrunk:", a);
        std::println("  expected {}, got {}", brute(a), fast(a));
        return;
    }
    std::println("{}: {} tests, all agree", name, tests);
}

int main() {
    stress("two largest", twoLargest, 5000);
    stress("largest or smallest", largestOrSmallest, 5000);
}
Output

Press Run to compile and run this example.

two largest: wrong on test 3
  found:  [ 4 -3 0 8 -4 -9 ]
  shrunk: [ 8 -4 -9 ]
  expected 36, got -32
largest or smallest: 5000 tests, all agree

The random input of six numbers already fails, but it takes a moment to see why. The shrunk input does not: with [8, -4, -9] the two largest values are 8 and -4, product -32, while the two negatives multiply to 36. Three elements is as small as it gets, because with two elements there is only one pair and both versions find it. The fix is to compare the product of the two largest with the product of the two smallest, and the second run checks it on 5,000 inputs.

A few things make a harness like this effective:

  • Small inputs. Sizes from 2 to 8 and values from -9 to 9 hit edge cases (duplicates, zeros, all negative, the minimum size) far more often than large random data does, and failures stay readable.
  • A fixed seed. The same seed gives the same tests, so a failure can be reproduced after you change the code. Change the seed, or loop over several, to explore more.
  • A generator that covers the whole input space. If the generator produced only non-negative numbers, this bug would never show. Look at the constraints and make sure every kind of value they allow can appear.
  • Shrinking. Automatic shrinking as above, or by hand: copy the failing input, delete a number, rerun, and keep the deletion if it still fails. A minimal case usually names the bug.

When the brute force and the solution are in different files, the same loop works with a shell script that runs a generator, both programs, and compares outputs. Keeping all three in one file, as here, is simpler and works in the playground.

Previous
Complexity in Practice: Reading Constraints and Choosing an Algorithm
Next
Graphs: BFS, DFS, Connected Components and Topological Sort