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 perform more than 1 billion elementary operations (addition, subtraction, multiplication, and bit manipulation for integers or floating-point numbers) in less than 1 second. Keep in mind that divisions are much slower than multiplications.

Arrays are great for performance, especially if they fit in cache or if you access them linearly. With small arrays, you can expect to perform hundreds of millions of array updates in less than 1 second.

Sorting with std::sort is also surprisingly fast; you can expect 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 much more than a few million hash-table updates (for example, in std::unordered_set and std::unordered_map) per second. Tree-based data structures (for example, std::set and std::map) are even slower.

You can easily read and write millions of numbers per second, but only if you use std::ios_base::sync_with_stdio(0).

Posting submission...