jt.cheng26_orz's blog

By jt.cheng26_orz, 3 months ago, In English

Both scanf/printf and cin/cout (with stdio sync optimization on) are pretty fast on their own. However, there is a way to keep the easy grammatical syntax of cin/cout while still obtaining a 4x speedup.

Firstly, let us look at the functions getchar_unlocked() and putchar_unlocked(). These functions provide an immense speedup to the default getchar() or putchar() functions, which are already fast themselves. The following class/template will wrap those functions, and with overloaded << and >> operators, we can easily replicate the syntax of cin and cout.

Template, just copy paste this into your program

Unfortunately the FastIO class cannot read doubles, if anyone could offer advice that would be great!

This was tested on Ciel and Gondolas, which is a very input heavy problem. The FastIO class passed with 872 ms, while optimized cin/cout passed with 3212 ms, and scanf/printf straight up TLE'd.

 
 
 
 
  • Vote: I like it
  • +66
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Just tested my fastio template, and it passed in 498ms. No need for fast output because this problem only needs you to print one number. With minor improvements I got it to 466ms, but I think by that point I/O isn't the bottleneck.

This is better for interactive problems though, because my solution uses fread (and I think getchar works for interactive problems).

Also, I have no idea why this is faster than your fastio, because it does basically the same thing (it just isn't in a struct for me).

One improvement: You have read(int32_t), read(int64_t), and read(__int128) each as separate functions, and the same thing for print. Maybe you could use templates to make that shorter and more readable? Or maybe use a macro like READ(int32_t) if you don't want to use std::enable_if<> magic.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for the suggestion! I will try to update tomorrow if I have time.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Ok so I tried your template and got a compilation error, then noticed that I need to submit it C++17 (64) and not just C++17. Link.

I use VSCode + CPH so this is how it compiles. Link.

What should i add so it is equivalent to the CF C++17 (64) on my local?

(I get this error, which is the same as the CE on Codeforces too. but same passes in (64))

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I get to know about this a year ago, but I don't remember why I stopped using it on regular basis.

Ya, It helps with many problems.

Without this, you will get TLE
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it
    but I don't remember why I stopped using it on regular basis

    Because that's when you started doing this on a regular basis.

»
3 months ago, # |
Rev. 14   Vote: I like it 0 Vote: I do not like it

Check the implementation of the template functions get_flt and put_flt in the following submission.

127652820

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got 374ms using my (rudimentary) fastio template here: 127665247. Some stylistic suggestions:

  1. Try using templates, they make life much easier if you have a lot of similar types to implement functions for.
  2. You're leaking small amounts of memory each time you run the program, you might as well just make a simple array (or a vector if you want dynamic allocations, but that doesn't make sense to me).