Finally, justice has been served to Bob!! 😭

In 2272F — Tree Reduction Game, Alice still gets the first move, but Bob finally gets some compensation: he can choose the initial root of the tree!

With the right choice, Bob can guarantee his victory even when playing second. No more suffering from always going second — Bob is finally getting his chance to shine!

Justice for Bob at last. 🗿

Fast I/O in C++: A Practical Guide

In Competitive Programming, Fast I/O is one of those things that people either use everywhere or completely ignore. Usually, ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); is already enough, but when the input and output become really large, a custom implementation can make a noticeable difference.

The main idea is simple: avoid doing expensive I/O work more often than necessary. A common approach is to read a large block with fread, keep it in memory, and parse the characters directly. For output, we do the opposite: write into a buffer and flush it with fwrite when the buffer is full.

Here is the Fast I/O implementation I currently use:

typedef long long ll;
typedef unsigned long long ull;

#define fast
#ifdef fast
struct FastIO {
	int prec = 6;
	char ib[1 << 21], ob[1 << 21], *p1 = ib, *p2 = ib, *p3 = ob;
	~FastIO() { flush(); }
	inline int gc() { return (p1 == p2 && (p2 = ib + fread(ib, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++); }
	inline void pc(char c) { if (p3 == ob + (1 << 21)) flush(); *p3++ = c; }
	inline void flush() { if (p3 != ob) fwrite(ob, 1, p3 - ob, stdout), p3 = ob; }
	template<typename T> FastIO& operator>>(T &x) {
		x = 0; int f = 1, c = gc();
		while (c < '0' || c > '9') { if (c == '-') f = -1; if (c == EOF) return *this; c = gc(); }
		while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
		return x *= f, *this;
	}
	FastIO& operator>>(char &c) { c = gc(); while (c <= 32 && c != EOF) c = gc(); return *this; }
	FastIO& operator>>(double &x) {
		x = 0; double f = 1, dec = 1; int c = gc();
		while (c < '0' || c > '9') { if (c == '-') f = -1; if (c == EOF) return *this; c = gc(); }
		while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = gc();
		if (c == '.') while ((c = gc()) >= '0' && c <= '9') x += (c ^ 48) * (dec /= 10);
		return x *= f, *this;
	}
	FastIO& operator>>(long double &x) {
		x = 0; long double f = 1, dec = 1; int c = gc();
		while (c < '0' || c > '9') { if (c == '-') f = -1; if (c == EOF) return *this; c = gc(); }
		while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = gc();
		if (c == '.') while ((c = gc()) >= '0' && c <= '9') x += (c ^ 48) * (dec /= 10.0L);
		return x *= f, *this;
	}
	FastIO& operator>>(string &s) {
		s = ""; int c = gc(); while (c < 33 && c != EOF) c = gc();
		while (c > 32) s += c, c = gc(); return *this;
	}
	template<typename T> FastIO& operator<<(T x) {
		if (!x) return pc('0'), *this;
		if (x < 0) pc('-'), x = -x;
		ull t = x; static char s[40]; int l = 0;
		while (t) s[l++] = (t % 10) ^ 48, t /= 10;
		while (l--) pc(s[l]); return *this;
	}
	FastIO& operator<<(double x) {
		if (x < 0) pc('-'), x = -x;
		double rd = 0.5; for (int i = 0; i < prec; i++) rd /= 10.0;
		x += rd; *this << (ll)x;
		if (prec > 0) { pc('.'); x -= (ll)x; for (int i = 0; i < prec; i++) { x *= 10; pc(((int)x) ^ 48); x -= (int)x; } }
		return *this;
	}
	FastIO& operator<<(long double x) {
		if (x < 0) pc('-'), x = -x; long double rd = 0.5;
		for (int i = 0; i < prec; i++) rd /= 10.0L;
		x += rd; ull integer_part = (ull)x; *this << integer_part;
		if (prec > 0) { 
			pc('.'); x -= (long double)integer_part;
			for (int i = 0; i < prec; i++) { 
				x *= 10.0L; int digit = (int)x; pc(digit ^ 48); x -= (long double)digit; }
		}
		return *this;
	}
	FastIO& operator<<(char c) { return pc(c), *this; }
	FastIO& operator<<(string s) { for (char c : s) pc(c); return *this; }
	FastIO& operator<<(const char *s) { while (*s) pc(*s++); return *this; }
	void setpre(int p) { prec = p; }
} f_io;
#define cin f_io
#define cout f_io
#endif

#ifndef fast
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#endif

There are a few details in this code that are worth understanding instead of blindly copying it.

First, the two arrays ib and ob are the actual I/O buffers. ib stores a chunk of input, while ob stores output until it is time to flush. The size here is 1 << 21, which is 2 MiB.

For input, gc() refills ib using fread whenever the current buffer has been consumed. It returns one character at a time, but its return type is int rather than char. This is important because gc() can also return EOF, whose value is -1.

Using int here avoids a subtle problem: if char is unsigned on the target platform, returning EOF as a char would convert -1 into a positive value. Conditions such as c == EOF could then fail.

The integer parser uses

(x << 3) + (x << 1)

to compute x * 10. It is just a bitwise way of writing x * 8 + x * 2.

The character expression

c ^ 48

converts a digit character such as '7' to the integer 7. This works because the ASCII codes of '0' through '9' are consecutive, with '0' equal to 48.

For example:

'7' ^ '0'

is equivalent to:

55 ^ 48

which gives 7.

c - '0' would be clearer for most readers, so this is mainly a low-level implementation/style choice rather than something that is necessary for Fast I/O.

The output side works in the opposite way. Instead of calling fwrite for every character, pc() writes characters into ob. Once the buffer is full, flush() writes the whole block at once. The destructor also calls flush(), so remaining output is written automatically when f_io is destroyed.

Another small detail is the static char s[40] used when printing integers. It is unrelated to the I/O buffer. It only stores the digits of the current number in reverse order before printing them. An unsigned long long needs at most 20 decimal digits, so 40 bytes gives the implementation plenty of room.

One edge case worth knowing about is signed integer output. The expression

x = -x;

cannot represent the positive counterpart of the minimum value of a signed integer type, such as LLONG_MIN. This normally does not matter in competitive programming because printed values are usually well inside the valid range, but it is something to keep in mind if you want a completely general-purpose implementation.

The floating-point output operators are also intentionally simple. They print a fixed number of digits controlled by prec and perform a small rounding adjustment before extracting the digits. They are convenient for competitive programming, but they are not intended to replace a full-featured floating-point formatter.

So, do we actually need a custom Fast I/O class in every problem? Definitely not. For normal Codeforces problems, I would start with:

ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);

Only when I/O itself becomes a measurable bottleneck does a custom fread/fwrite implementation start to make sense.

Fast I/O is not a replacement for a good algorithm. Saving a fraction of a second on input is not going to turn an O(n^2) solution into an O(n log n) one. But when I/O really is the bottleneck, understanding what is happening underneath can make a surprisingly large difference.