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 (0M10\le M\le 1) and NN (1N1061\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
PlatinumInsane

Standard I/O

Slow

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

Scanner + System.out.println (16.7s)

Fast

Use BufferedReader and PrintWriter instead.

BufferedReader + PrintWriter (1.2s)

File I/O

Pretty similar to standard I/O.

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)

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)

Problems

StatusSourceProblem NameDifficultyTags
CFNormal

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!

PrevNext