# Cod sursa(job #2160250)

Utilizator Data 11 martie 2018 12:15:11 Hashuri 0 cpp done Arhiva educationala 2.9 kb
``````#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define Nmax 1000010
#define P 1000000009
#define M 300007

int H1[M+5][4], H2[M+5][4], S[Nmax], op, T, X ;
long long A1, A2, B1, B2 ;

int search ( int X )
{
int i ;
long long h1, h2 ;

h1 = ( (A1 * X + B1) % P ) % M ;
h2 = ( (A2 * X + B2) % P ) % M ;

for( i = 0 ; i < 4 ; i++ )
if( H1[h1][i] == X || H2[h2][i] == X )
return 1 ;

return 0 ;
}

void make_hash() ;

void insert ( int X )
{
int i ;
long long h1, h2 ;

h1 = ( (A1 * X + B1) % P ) % M ;
h2 = ( (A2 * X + B2) % P ) % M ;

for( i = 0 ; i < 4 ; i++ )
if( H1[h1][i] == X || H2[h2][i] == X ) return ;

for( i = 0 ; i < 4 ; i++ )
if( !H1[h1][i] )
{
H1[h1][i] = X ;
return ;
}
else if( !H2[h2][i] )
{
H2[h2][i] = X ;
return ;
}

make_hash();
}

void erase ( int X )
{
int i,j ;
long long h1, h2 ;

h1 = ( (A1 * X + B1) % P ) % M ;
h2 = ( (A2 * X + B2) % P ) % M ;

for( i = 0 ; i < 4 ; i++ )
if( H1[h1][i] == X )
{
for( j = i ; j < 3 ; j++ )
H1[h1][j] = H1[h1][j+1];
H1[h1][j] = 0 ;
}
else
if( H2[h2][i] == X )
{
for( j = i ; j < 3 ; j++ )
H2[h2][j] = H2[h2][j+1];
H2[h2][j] = 0 ;
}
}

void make_hash ()
{
int i,j;

int N = 0 ;

for( i = 0 ; i < M ; i++ )
for( j = 0 ; j < 4 ; H1[i][j] = H2[i][j] = 0 , j++ )
if( H1[i][j] )
S[++N] = H1[i][j] ;

A1 = rand() % P ;
A2 = rand() % P ;
B1 = rand() % P ;
B2 = rand() % P ;

for( i = 1 ; i <= N ; i++ )
insert( S[i] ) ;
}
int main ()
{
srand(time(0));

freopen("hashuri.in","r",stdin);
freopen("hashuri.out","w",stdout);

scanf("%d",&T);

make_hash() ;

while( T-- )
{
scanf("%d %d",&op,&X) ;

switch(op)
{
case 1:
insert(X); break ;
case 2:
erase(X); break ;
case 3:
printf("%d\n",search(X)); break ;
}
}

return 0 ;
}``````