PrevNext

Fast Input & Output

Authors: Benjamin Qi, Nathan Chen

Demonstrates how I/O speed can be the difference between TLE and AC.

Edit This Page

The USACO Instructions Page briefly mentions some ways of speeding up I/O:

For some of the more advanced problems with larger input sizes, competitors may benefit from using fast input/output, to more easily pass within the time limit. For C++ users, you may want to add "ios_base::sync_with_stdio(false); cin.tie(0);" to the top of your main method if you are using cin/cout. For Java users, you may want to use BufferedReader instead of Scanner.

What do these do and how much of a difference do these actually make? We'll use the following task to benchmark I/O speed:

Example Task

The input consists of two integers MM (0≤M≤10\le M\le 1) and NN (1≤N≤1061\le N\le 10^6), followed by a sequence of NN non-negative integers each less than 109+710^9+7.

  • If M=0M=0, output the sum of the input sequence modulo 109+710^9+7.
  • If M=1M=1, output the sum of each prefix of the input sequence modulo 109+710^9+7.

Sample Input 1:

1 6
1
2
3
4
5
1000000000

Sample Output 1:

1
3
6
10
15
8

Sample Input 2:

0 6
1
2
3
4
5
1000000000

Sample Output 2:

8

Randomly generating test data results in input and output files each ~10MB large. It is possible to see input files this large (the 11th input file for Robotic Cow Herd is ~10.3MB large), though not output files (the largest we know of is due to Minimum Cost Paths, which has an output file ~2.8MB large).

StatusSourceProblem NameDifficultyTags
Plat
Robotic Cow Herd
Insane

Standard I/O

Slow

Some simple methods of I/O don't come close to running under the time limit:

C++

cin/cout + endl (5.8s)

Java

Scanner + System.out.println (16.7s)

Python

input + print (18.9s)

Fast

C++

cin/cout

If using cin and cout, include the following two lines.

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

Brief explanation:

  • If you include ios::sync_with_stdio(false), then mixing C (scanf, printf) and C++ (cin, cout) style I/O may produce unexpected results. The upside is that both cin / cout become faster.
  • Including cin.tie(nullptr) will reduce the runtime if you are interleaving cin and cout (as is the case in the task at hand).

You can find more information about these lines at the end of this module.

cin/cout + unsync + \n (0.41s)

Warning!

Using endl instead of "\n" will flush the output buffer and cause the above method to be quite slow:

cin/cout + unsync + endl (5.0s)

Though for interactive problems, you need to flush the output buffer every time you use cout. Any one of the following will have the same effect:

  1. Not including cin.tie(nullptr)
  2. Writing cout << endl instead of cout << "\n"
  3. Writing cout << "\n" << flush instead of cout << "\n"

scanf/printf

scanf/printf (0.52s)

Java

Use BufferedReader and PrintWriter instead.

BufferedReader + PrintWriter (1.2s)

Python

Replacing input with sys.stdin.readline results in a huge speedup.

readline + print (2.9s)

Using sys.stdin.readline and sys.stdout.write is a bit faster:

readline + write (2.4s)

File I/O

Pretty similar to standard I/O.

C++

Slow

freopen + cin/cout (5.7s)

Fast

freopen + cin/cout + unsync + \n (0.42s)

freopen + scanf/printf (0.52s)

ifstream/ofstream (0.43s)

Java

Slow

Scanner + PrintWriter (3.4s)

Fast

BufferedReader + PrintWriter (1.2s)

A variant of the above method involves wrapping the BufferedReader with a StreamTokenizer:

StreamTokenizer (1.2s)

Python

readline + write (2.4s)

C++

Even Faster Methods

The input methods described above are easy to type up from scratch and are usually fast enough for USACO contests. But if you're looking for something even faster ...

Using fread and fwrite reduces the runtime even further.

fread/fwrite (0.17s)

Java

Even Faster Methods

The input methods described above are easy to type up from scratch and are usually fast enough for USACO contests. But if you're looking for something even faster ...

Even faster than BufferedReader is a custom-written Fast I/O class that reads bytes directly from an InputStream.

InputStream + PrintWriter (0.84s)

Python

C++

Additional Notes

Resources
CF
Yet again on C++ I/O

timing various I/O methods

ios::sync_with_stdio(false)

Resources
CPP
ios_base::sync_with_stdio

documentation

SO
Significance of ios_base::sync_with_stdio(false);

From the second resource:

This disables the synchronization between the C and C++ standard streams. By default, all standard streams are synchronized, which in practice allows you to mix C- and C++-style I/O and get sensible and expected results. If you disable the synchronization, then C++ streams are allowed to have their own independent buffers, which makes mixing C- and C++-style I/O an adventure.

cin.tie(nullptr)

Resources
CPP
ios::tie

documentation

SO
Significance of cin.tie(NULL);

From the second resource:

This unties cin from cout. Tied streams ensure that one stream is flushed automatically before each I/O operation on the other stream.

By default cin is tied to cout to ensure a sensible user interaction. For example:

std::cout << "Enter name:";
std::cin >> name;

If cin and cout are tied, you can expect the output to be flushed (i.e., visible on the console) before the program prompts input from the user. If you untie the streams, the program might block waiting for the user to enter their name but the "Enter name" message is not yet visible (because cout is buffered by default, output is flushed/displayed on the console only on demand or when the buffer is full).

So if you untie cin from cout, you must make sure to flush cout manually every time you want to display something before expecting input on cin.

Warning: cout.tie(nullptr)

You may see some competitive programmers including this line. This doesn't actually do anything since cout isn't tied to anything. See this post for details.

Java

Python

Problems

StatusSourceProblem NameDifficultyTags
CF
Soldier and Number Game
Normal

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum
PrevNext