#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdio>
using namespace std;
template <class T>
class blablaHashing{
public:
blablaHashing(int, string, string);
~blablaHashing();
bool operator+(T &);
bool operator[](T &);
void operator-(T &);
void start();
private:
FILE *in, *out;
T *table1, *table2;
protected:
int loopLimit, random1, random2, sizeHash;
int random3, random4, intrebare;
void swap(T &,T &);
void changeHashingFunction();
virtual int funct1(T &)=0;
virtual int funct2(T &)=0;
};
class intHash:public blablaHashing<int>{
public:
intHash(int n, string fin, string fout): blablaHashing<int>(n, fin, fout){};
private:
int funct1(int &);
int funct2(int &);
};
class doubleHash:public blablaHashing<double>{
public:
doubleHash(int n, string fin, string fout): blablaHashing<double>(n, fin, fout){};
private:
int funct1(double &);
int funct2(double &);
};
class floatHash:public blablaHashing<float>{
public:
floatHash(int n, string fin, string fout): blablaHashing<float>(n, fin, fout){};
private:
int funct1(float &);
int funct2(float &);
};
class charHash:public blablaHashing<char>{
public:
charHash(int n, string fin, string fout): blablaHashing<char>(n, fin, fout){};
private:
int funct1(char &);
int funct2(char &);
};
int main (){
srand((unsigned)time(NULL));
blablaHashing<int> *Hash;
Hash = new intHash (1000111, "hashuri.in", "hashuri.out");
Hash->start();
return 0;
}
template <class T>
blablaHashing<T>::blablaHashing(int n, string fin, string fout){
sizeHash = n;
in = fopen(fin.c_str(), "rt");
out = fopen(fout.c_str(), "wt");
table1 = new T [n];
table2 = new T [n];
loopLimit = 25;
}
template <class T>
inline void blablaHashing<T>::start(){
changeHashingFunction();
int M, op;
T x;
fscanf (in, "%d", &M);
while (M--){
fscanf (in , "%d%d", &op, &x);
if (op == 1){
if(!(*this)[x]) {
bool ok;
ok = *this + x;
if (!ok) {
rewind(in);
rewind(out);
start();
return;
}
}
continue;
}
if (op == 2){
if ((*this)[x]) *this - x;
continue;
}
if ((*this)[x]) fprintf (out, "1\n");
else fprintf (out, "0\n");
}
}
template <class T>
inline bool blablaHashing<T>::operator[](T & x){
int func1 = funct1(x);
if (table1[func1] == x) return true;
int func2 = funct2(x);
if (table2[func2] == x) return true;
else return false;
}
template <class T>
inline void blablaHashing<T>::operator-(T & x){
int func1 = funct1(x);
if (table1[func1] == x) {
table1[func1] = 0;
return;
}
int func2 = funct2(x);
table2[func2] = 0;
return;
}
template <class T>
inline bool blablaHashing<T>::operator+(T & x){
int tAux1, tAux2;
tAux1 = funct1(x);
if(!table1[tAux1]){
table1[tAux1] = x;
return true;
}
tAux2 = funct2(x);
for (int i = 1; i <= loopLimit; i+=2){
if (!table2[tAux2]){
table2[tAux2] = x;
return true;
}
swap(x, table2[tAux2]);
tAux1 = funct1(x);
if (!table1[tAux1]){
table1[tAux1] = x;
return true;
}
swap(x, table1[tAux1]);
tAux2 = funct2(x);
}
return false;
}
template <class T>
blablaHashing<T>::~blablaHashing(){
delete []table1;
delete []table2;
fclose(in);
fclose(out);
}
template <class T>
inline void blablaHashing<T>::changeHashingFunction(){
random1 = rand()%sizeHash;
random2 = rand()%sizeHash;
random3 = rand()%sizeHash;
random4 = rand()%sizeHash;
memset(table1, 0, sizeof(table1));
memset(table2, 0, sizeof(table2));
}
inline int intHash::funct1(int & x){
return ((x * random1) % random2 + x ) % sizeHash;
}
inline int intHash::funct2(int & x){
return ((x * random3) % random4 + x ) % sizeHash;
}
inline int charHash::funct1(char &x){
return (((long long)x * (long long)random1) % (long long)random2 + (long long)x ) % sizeHash;
}
inline int charHash::funct2(char &x){
return (((long long)x * (long long)random3) % (long long)random4 + (long long)x ) % sizeHash;
}
inline int doubleHash::funct1(double &x){
while (floor(x) != ceil(x) ){
x = (x * 10);
}
return (((int)x * random1) % random2 + (int)x ) % sizeHash;
}
inline int doubleHash::funct2(double & x){
while (floor(x) != ceil(x) ){
x = (x * 10);
}
return (((int)x * random3) % random4 + (int)x ) % sizeHash;
}
inline int floatHash::funct1(float &x){
while (floor(x) != ceil(x) ){
x = (x * 10);
}
return (((int)x * random1) % random2 + (int)x ) % sizeHash;
}
inline int floatHash::funct2(float &x){
while (floor(x) != ceil(x) ){
x = (x * 10);
}
return (((int)x * random3) % random4 + (int)x ) % sizeHash;
}
template <class T>
inline void blablaHashing<T>::swap(T &a,T &b){
int tempAux = a;
a = b;
b = tempAux;
}