// 03.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::ofstream;

void ReadInputValues(vector<int> *values)
    {
    int count;
    cin>>count;
    values->resize(count);
    for(int i = 0; i < count; ++i) {
        scanf("%d",&(*values)[i]);
        }
    }

void ReadInputQuestions(vector<int> *questions) {
    int count;
    cin>>count;
    questions->resize(count);
    for(int i=0;i<count;++i) {
        scanf("%d", &(*questions)[i]);
        }
    }

class FixedSet {
private:
    struct HashFunctionParameters {
     int a;
     int b;
    };

    vector<vector<int> > hashTable;
    vector<HashFunctionParameters> secondLevelParameters;
    HashFunctionParameters firstLevelParameters;

    void InitializeFirstLevelHashFunction(const vector<int> &values);
    void InitializeSecondLevelHashFunctions();

    //((ax+b)mod p)mod n
    static unsigned int UniversalHashFunction( int x, const HashFunctionParameters& parameters,  int primeNumber,  int elementCount);
    static void GetHashFunctionParameters(HashFunctionParameters *parameters,  int primeNumber);
public:
    static const int PRIME_NUMBER = 2147000041;
    static const int OUT_OF_RANGE_VALUE = 1000000001;
    static const int LINEAR_MEMORY_COEFFICIENT = 4;

    void Initialize(const vector< int> &values);
    bool Contains( int value) const;
    };

unsigned int FixedSet::UniversalHashFunction( int x, const HashFunctionParameters& parameters,  int primeNumber,  int elementCount) {
    long long primeNumberRemainder = (static_cast<long long>(parameters.a) * x + parameters.b) % primeNumber;
    primeNumberRemainder = primeNumberRemainder < 0 ? (primeNumberRemainder + primeNumber) : primeNumberRemainder;
    return primeNumberRemainder % elementCount;
    }

void FixedSet::GetHashFunctionParameters(HashFunctionParameters *parameters,  int primeNumber) {
    parameters->a = rand();
    parameters->a <<= 16;
    parameters->a |= rand();
    parameters->a &= ((unsigned int)(-1) >> 1);
    parameters->a %= primeNumber - 1;
    parameters->a += 1;

    parameters->b = rand();
    parameters->b <<= 16;
    parameters->b |= rand();
    parameters->b &= ((unsigned int)(-1) >> 1);
    parameters->b %= primeNumber;
    }

void FixedSet::InitializeFirstLevelHashFunction(const vector<int> &values) {
    //looking for the first level hash function
    long long sum = 0;
    do {
        for(vector<vector<int> >::iterator iter = hashTable.begin(); iter != hashTable.end(); ++iter) {
            (*iter).resize(0);
            }
        GetHashFunctionParameters(&firstLevelParameters, PRIME_NUMBER);
        for(vector<int>::const_iterator iter = values.begin(); iter!=values.end(); ++iter) {
            size_t index = UniversalHashFunction(*iter, firstLevelParameters, PRIME_NUMBER, values.size());
            hashTable[index].push_back(*iter);
            }
        sum = 0;
        for(vector<vector<int> >::const_iterator iter = hashTable.begin();iter != hashTable.end(); ++iter) {
            sum += static_cast<long long>((*iter).size()) * (*iter).size();
            }
        } while(sum > LINEAR_MEMORY_COEFFICIENT * values.size());
    }

void FixedSet::InitializeSecondLevelHashFunctions() {
    //second level hash functions
    vector<HashFunctionParameters>::iterator hashParametersIterator = secondLevelParameters.begin();
    vector<vector<int> >::iterator hashTableIterator = hashTable.begin();
    for(; hashTableIterator != hashTable.end() && hashParametersIterator != secondLevelParameters.end(); ++hashTableIterator, ++hashParametersIterator) {
        vector< int> bucketCopy;
        HashFunctionParameters params;
        bucketCopy.resize((*hashTableIterator).size() * (*hashTableIterator).size());

        bool collisionsExist;
        do {
            collisionsExist = false;
            fill(bucketCopy.begin(), bucketCopy.end(), OUT_OF_RANGE_VALUE);
            GetHashFunctionParameters(&params, PRIME_NUMBER);
            for(vector<int>::const_iterator bucketItem = bucketItem = (*hashTableIterator).begin(); bucketItem != (*hashTableIterator).end(); ++bucketItem) {
                size_t position = UniversalHashFunction(*bucketItem, params, PRIME_NUMBER, bucketCopy.size());
                if(bucketCopy[position] == OUT_OF_RANGE_VALUE) {
                    bucketCopy[position] = *bucketItem;
                    }
                else if(bucketCopy[position] != *bucketItem) {
                    collisionsExist = true;
                    break;
                    }
                }
            } while(collisionsExist);

        (*hashParametersIterator) = params;
        (*hashTableIterator) = bucketCopy;
        }
    }

void FixedSet::Initialize(const vector< int> &values) {
    hashTable.resize(values.size());
    secondLevelParameters.resize(values.size());

    InitializeFirstLevelHashFunction(values);
    InitializeSecondLevelHashFunctions();
    }

bool FixedSet::Contains( int value) const {
    size_t firstPos = UniversalHashFunction(value, firstLevelParameters, PRIME_NUMBER, hashTable.size());
    if(hashTable[firstPos].size() == 0)
        return false;
    else
        {
        HashFunctionParameters ps = secondLevelParameters[firstPos];
        size_t secondPos = UniversalHashFunction(value, ps, PRIME_NUMBER, hashTable[firstPos].size());
        return hashTable[firstPos][secondPos] == value;
        }
    }

void FindNumbers(const FixedSet &set, const vector<int> &questions, vector<bool> *answers) {
    answers->resize(questions.size());
    vector<int>::const_iterator questionsIterator = questions.begin();
    vector<bool>::iterator answersIterator = answers->begin();
    for(; questionsIterator != questions.end() && answersIterator != answers->end(); ++questionsIterator, ++answersIterator) {
        *answersIterator = set.Contains(*questionsIterator);
        }
    }

void PrintAnswers(const vector<bool> &answers) {
    for(vector<bool>::const_iterator iter = answers.begin(); iter != answers.end(); ++iter) {
        *iter ? printf("Yes\n") : printf("No\n");
        }
    }

int main()
{
    srand(239);

    vector<int> numbers;
    vector<bool> answers;

    for(int i=0;i<<100000;++i)
        {
        numbers.push_back(i);
        }

    FixedSet set;
    set.Initialize(numbers);

    for(int i=0;i<100000;++i)
        {
        if(!set.Contains(i))
            {
            cout<<"error";
            return 0;
            }
        }

    return 0;
}