dmkz's blog

By dmkz, history, 6 years ago, In English

Hi! Maybe someone wants to realize crazy ideas using uint128_t during contest. I implemented some functionality (<<,>>,-,+,*,%,/) and tested on problem 984C. Finite or not?. If there are any bugs or optimizations which can reduce runtime, please tell.

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow. I wanted to say smth like "g++ already has int128", but CF has only 32-bit g++
Thank you, author =)

If there are any bugs or optimizations

There are. I will comment only IO-part. Marks TL / WA mean type of comment.
Spoiler: nothing very important.

TL void putStr(std::string s)

Use const &s, do not make copy of s.

TL putStr(solve(p,q,b).c_str());

You convert stringchar*string :D
Any way, it is useful to have also void putStr(const char* s)

TL void putInt(T number) { putStr(std::to_string(number)); }

If you wanna be really fast, do not convert to string. At least, you create one extra string object.

TL static char buffer[1024*1024];

If you make buffer less (16K), caching will speed up in some cases.

WA T getInt(): return number * sign;

It leads to undefined behavior if you try to read int =  -231. About signed integer overflow.

WA void putChar(char c): if (size == 1024 * 1024 || c == -1)

Nice solution to flush buffer. Note, char c = -1 is rare but correct symbol ('я' in win1251).
So it's better to make void putChar(int c)

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for your reply! This blogpost was targeted to uint128_t, so I just wrote fast I/O in 5-10 minutes for this problem only. I think that we need to find safe and fast solution for fast I/O in minimal number of lines in code. I already wrote something for fast I/O and tested in this comment3x speed up in comparison with scanf / printf and cin/cout, you can check it.