// Double Hash
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cassert>
#define maxh 666013
#define maxh2 200003


int H1[maxh][4], H2[maxh2][4];
char len1[maxh], len2[maxh2];

inline int find(int v)
{
	int h1=v%maxh;
	int h2=v%maxh2;
	
	//assert(len1[h1] <= 4);
    //assert(len2[h2] <= 4);
	
	for(int i=0; i < len1[h1]; ++i)
		if(H1[h1][i] == v) return 1;
	
	for(int i=0; i< len2[h2]; ++i)
		if(H2[h2][i] == v) return 1;
	return 0;
}

inline void insert(int v)
{
	if(find(v)) return ;

	int h1=v%maxh;
	int h2=v%maxh2;
	
	if(len1[h1] < len2[h2])
		H1[h1][len1[h1]++]=v;
	else
		H2[h2][len2[h2]++]=v;
}

int a[1000001];
int n=1000000;

int main()
{
	srand(time(0));
	
	int i;
	for(i=1;i<=n;++i) a[i]=rand()*rand();
	
	double s=clock();
	
	for(i=1;i<=n;++i) insert(a[i]);
	for(i=1;i<=n;++i) find(a[i]);
	for(i=1;i<=n;++i) find(rand()*rand());
	
	printf("Time: %lf\n", (clock()-s)/(double)CLOCKS_PER_SEC);
	
	
	int t=sizeof(H1) + sizeof(H2) + sizeof(len1)+ sizeof(len2);
	t/=1024;
	printf("%d MB\n", t/1024);
	return 0;
}