Data types, I/O (cin/cout) & fast I/O tricks
Scenario
You write a competitive programming solution that is mathematically optimal (O(N)), but it gets Time Limit Exceeded (TLE) anyway.
Why did a linear-time algorithm fail?
Mental model
Standard I/O in C++ is tied to C's stdio for safety, and endl flushes the output buffer every single time. It's like driving a truck to the post office for every single letter instead of filling the truck first.
C++ I/O streams (cin, cout) are synchronized with C's stdio (printf, scanf) by default so you can mix them safely. This synchronization adds massive overhead. Furthermore, std::endl does two things: it inserts a newline, AND it flushes the output buffer to the console. When printing thousands of lines, flushing every line causes severe performance degradation. The fix is to untie the streams and use '\n'.
Explanation
In performance-critical scenarios, especially competitive programming, I/O speed can be the bottleneck. By default, `std::cin` and `std::cout` are tied together (reading from `cin` automatically flushes `cout`) and synchronized with C's underlying I/O buffers. This guarantees that if you mix `printf` and `cout`, the output appears in the correct order. But this thread-safe synchronization is slow.
We can disable it using `std::ios_base::sync_with_stdio(false);`. Once you do this, you must NOT mix C and C++ I/O functions. Additionally, `std::cin.tie(nullptr);` prevents `cin` from flushing `cout` before every read, which is safe when you don't need interactive prompts.
The second major trap is `std::endl`. It writes a newline character and forces a flush of the output buffer. Flushing is a heavy system call. When you only need a newline, use the character `'\n'`. The buffer will still flush automatically when it's full or when the program terminates, which is far more efficient.
Code examples
The bug: slow I/O and excessive flushing
#include <iostream>
int main() {
int n;
std::cin >> n;
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
// std::endl flushes the buffer on every iteration
std::cout << (x * 2) << std::endl;
}
return 0;
}If `n` is 10^5, this program makes 100,000 system calls to flush the output. Additionally, `cin` and `cout` are synchronized with C's `stdio`, adding overhead to every single read and write.
The fix: fast I/O template and '\n'
#include <iostream>
int main() {
// Untie C and C++ streams. Do not mix printf/scanf with cin/cout after this!
std::ios_base::sync_with_stdio(false);
// Prevent cin from automatically flushing cout before every read.
std::cin.tie(nullptr);
int n;
std::cin >> n;
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
// '\n' just appends a newline to the buffer; flush happens only when full.
std::cout << (x * 2) << '\n';
}
return 0;
}Adding the two fast I/O lines and replacing `std::endl` with `'\n'` can speed up I/O by orders of magnitude. This is the standard boilerplate for any C++ competitive programming template.
Key points
- Always use '\n' instead of std::endl: Unless you explicitly need to flush the buffer (like in an interactive prompt or right before an expected crash), use `'\n'`.
- Fast I/O boilerplate: Use `std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);` in competitive programming to avoid TLE.
Common mistakes
- Mixing C and C++ I/O after untying: If you call `sync_with_stdio(false)` and then use both `std::cout` and `printf`, your output might appear out of order because they are now using separate, unsynchronized buffers.
- Using std::endl when debugging a crash: While `\n` is better for performance, `std::endl` is exactly what you want when debugging via print statements before a crash. If you use `\n`, the program might crash before the buffer flushes, and you won't see your debug output.
Recall questions
- What two things does std::endl do?
- Why is std::ios_base::sync_with_stdio(false) used in competitive programming?
- What is the danger of using sync_with_stdio(false)?
Questions & answers
A candidate writes a C++ solution that times out, but an equivalent Java solution passes. They are using `std::cin` and `std::cout` with `std::endl`. How would you review their code?
I would point out that `std::endl` forces a buffer flush on every line, and C++ streams sync with C streams by default. I'd advise replacing `std::endl` with `'\n'` and adding `std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);` to the start of `main`.
Approach: Identify the flush overhead of `endl` and the synchronization overhead of C++ streams as the hidden constant factors causing the TLE.
When building an interactive command-line tool, should you use `std::cin.tie(nullptr)`?
No. `cin` is tied to `cout` by default so that any pending output (like a prompt saying 'Enter your name:') is flushed before the program blocks to wait for input. Untying them might cause the program to wait for input before the prompt is actually printed.
Approach: Understand that untying `cin` and `cout` removes the automatic flush before reading, which breaks interactive prompts.