C++ tricks

Faster I/O

This may¹ speed up code execution, especially for problems with large dataset.

1
std::cin.tie(nullptr);
2
ios_base::sync_with_stdio(false);

Or an one-lined version

1
std::cin.tie(nullptr)->ios_base::sync_with_stdio(false);

Btw, cout is not tied to any streams so you don’t have to “untie” it.

There’s also a much faster variant of this technique, though not included here.

More compact 2D array dumping

1
for (int i = 1; i <= m; i++)
2
  for (int j = 1; j <= n; j++)
3
    std::cout << a[i][j] << " \n"[j == m];

It will end the line with either whitespace or newline, based on what j == m is evaluated to ( for 0 - false and \n for 1 - true).

“Superior” hashmap implementation

1
#include <ext/pb_ds/assoc_container.hpp>
2
using namespace __gnu_pbds;
3
gp_hash_table<int, int> table;

1
unordered_maplinear insertion: 0.689846
2
gp_hash_tablelinear insertion: 0.256131
3

4
unordered_maplinear read/write: 1.69783
5
gp_hash_tablelinear read/write: 0.26842
6

7
unordered_maprandom insertion: 2.90184
8
gp_hash_tablerandom insertion: 0.56553
9

10
unordered_maprandom read/write: 2.02336
11
gp_hash_tablerandom read/write: 0.403486

This data structure performs much faster than unordered_map in all respects, though maybe exclusive to gcc.

Source: https://codeforces.com/blog/entry/60737

Vector usage

1
int n = 1e3;
2
std::vector<int> a(n);

1
for (int &z : a)
2
  std::cin >> z;

1
std::vector<bool> a(1e9); // uses only like ~122MB

Algorithms

1
std::vector<int> divc(n+1);
2
int l = 1e7;
3
for (int i = 1; i <= l; i++)
4
  for (int j = i; j <= l; j += i)
5
    divc[j]++;

1
for (i = 1; i <= sqrt(l); i++)
2
  for (j = i; j <= l / i; j++)
3
    divc[i * j] += 1 + (i != j);