#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <cstdlib>
#include <ctime>
#include <cassert>

typedef unsigned long long ull;
typedef std::pair<int,ull> Hash;

struct getHash {
public:
	template <typename T, typename U>
	std::size_t operator()(const std::pair<T, U> &x) const
	{
		return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
	}
};

ull rand_ull() {
	ull res = 0;
	for (int i = 0; i < 6; ++i) {
		(res *= 1000) += (std::rand() % 1000);
	}
	return res;
}

int main() {
	std::srand(std::time(0));
	
	const int n = (int)4e6;
	
	std::vector<Hash> array(n);
	
	for (auto& it : array) {
		it = std::make_pair(std::rand() % (int)1e9, rand_ull());
	}
	
	std::vector<Hash> queries(n);
	
	for (auto& it : queries) {
		it = std::make_pair(std::rand() % (int)1e9, rand_ull());
	}
	
	double t = clock();
	
	std::unordered_set<Hash, getHash> hashtable;
	
	for (auto it : array) {
		hashtable.insert(it);
	}
	
	int count1 = 0;
	
	for (auto hash : queries) {
		count1 += hashtable.find(hash) != hashtable.end();
	}
	
	double time1 = (clock() - t) / CLOCKS_PER_SEC;
	
	t = clock();
	
	std::sort(array.begin(), array.end());
	
	int count2 = 0;
	
	for (auto hash : queries) {
		count2 += std::binary_search(array.begin(), array.end(), hash);
	}
	
	double time2 = (clock() - t) / CLOCKS_PER_SEC;
	
	assert(count1 == count2);
	
	fprintf(stdout, "size & queries = %d\n", n);
	fprintf(stdout, "     hashtable = %0.3fs\n", time1);
	fprintf(stdout, "sort+binsearch = %0.3fs\n", time2);
	
	return 0;
}