// #define FAST_ALLOCATOR_MEMORY 1e8 // количество байт
// #include "optimization.h"

#include <vector>
#include <random>
#include <iostream>
#include <ctime>

#include <iostream>
#include <utility> // For std::pair
#include <ext/pb_ds/assoc_container.hpp> // For gp_hash_table
#include <ext/pb_ds/tree_policy.hpp> // For tree_order_statistics_node_update

// Required for gp_hash_table
using namespace __gnu_pbds;

using namespace std;


#include <unordered_map>
#include <map>
#define forn(i, n) for (int i = 0; i < (int)(n); i++)

// {
// 	vector<int> a(10); // 4*10 + 8*3
// }
// ++++++...........
// |     |          |

void time(const char *s = 0) { 
	static double start = 0;
	fprintf(stderr, "%.2f %s\n", (clock() - start) * 1. / CLOCKS_PER_SEC, s ? s : "");
	start = clock();
}

const int N = 1e7 + 3;

// x=h[i] ---> value=f[i]
struct HashTable { // unordered_map<int, int>
	int64_t h[N];
	int f[N]; // 0
	int index(int64_t x) { // O(1)
		int i = x % N; // hash-function
		while (h[i] != 0 && h[i] != x)
			i = (i + 1) % N;
		return i;
	}
	int& operator[] (int64_t x) {
		int i = index(x);
		h[i] = x;
		return f[i];
	}
} table;

int main() {
	int n = N / 2;

	mt19937 gen(std::time(0));
	unordered_map<int64_t, int> 
		stupid_table(n + gen() % n);
	forn(i, n) {
		int64_t key = (int64_t)i * i;
		stupid_table[key] = i;
	}
	time("stupid");

	forn(i, n) {
		int64_t key = (int64_t)i * i;
		table[key] = i;
	}
	time("hashTable");

	map<int64_t, int> very_stupid_table;
	forn(i, n) {
		int64_t key = (int64_t)i * i;
		very_stupid_table[key] = i;
	}
	time("map");

    gp_hash_table<int, int> myHashTable;
	forn(i, n) {
		int64_t key = (int64_t)i * i;
		myHashTable[key] = i;
	}
	time("gp_hash_table");

	// int x = 3; // 0 <= x < N
	// a[x] = 2; // <x, value>
	// cout << a[x] << endl;	
	// x = 1e9; 
	// table[x] = 3;
	// cout << table[x] << endl;
	// x ---> hash(x) : 0..N-1
	// a[hash(x)] = value
}


