Hi everyone!

I don't know, maybe this topis was discussed on Codeforces but google didn't help me.

It seems that standart hash function in gcc works badly (for Visual C++ all is good).

For 0 ≤ x ≤ 2³² - 1

std::hash<int>()(x) == x 
std::hash<long long>()(x) == x

For any other number

std::hash<long long>()(x + (1LL << 32)) == x

For example code in spoiler works more than 10s on Codeforces because hashes of all numbers are equal to zero.

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    unordered_set<long long> d;
    int n = 1e5;
    long long t = 1LL << 32;
    for (int i = 0; i < n; i++) {
        d.insert(i * t);
    }
    cout << d.size() << endl;
}

What can we do without writing our own hash function?