C++¶
Please read (at least) the following parts of Competitive Programmer’s Handbook:
Section 1.1: Programming languages
Section 1.2: Input and output (note
std::ios::sync_with_stdio
)Section 1.3: Working with numbers (note
long long
)Section 1.4: Shortening code
Section 3.2: Sorting in C++
Section 4.5: Other structures: Bitset (note
std::bitset
)Section 10.1: Bit representation
Section 10.2: Bit operations (note
__builtin_popcount
etc.)Section 10.3: Representing sets
Section 10.4: Bit optimizations
What can I do in one second?¶
Modern C++ compilers produce very efficient machine code, and modern CPUs are very fast.
You can expect to do more than 1 billion elementary arithmetic operations (addition, subtraction, multiplication, and bit manipulation for integers or floating-point numbers) in less than 1 second. Just keep in mind that divisions are much slower than multiplications.
Arrays are great for performance, especially if the arrays are small (fit in caches) or if you do linear reading and writing. With small arrays, you can expect to do hundreds of millions of array updates in less than 1 second.
Sorting with std::sort
is also surprisingly fast; you can expect to be able to sort an array with 10 million elements in less than 1 second. Following a linked list can be as slow as sorting.
Do not expect to be able to do much more than some millions of updates in hash tables (e.g. std::unordered_set
and std::unordered_map
) per second. Tree-like data structures (e.g. std::set
and std::map
) are even worse.
You can easily read and write millions of numbers per second, but only if you use std::ios_base::sync_with_stdio(0)
.