#include <iostream>
#include <vector>
#include <cstdlib> // для функций rand() и srand()
#include <list>
using namespace std;

const int p = 2000000033;
const int c = 3;


int rand_int(int min, int max)
{
    static const double fraction = 1.0 / (static_cast<double>(RAND_MAX) + 1.0);
    // Равномерно распределяем рандомное число в нашем диапазоне
    return static_cast<int>(rand() * fraction * (max - min + 1) + min);
}

int uni_hash(int a, int b, int m, int key)
{
    return ((a * key + b) % p) % m;
}

struct vertex
{
    bool visited = false;
    vector<struct adj_vertex> adj_list;
    int list_size = 0;
    int label;
};

struct adj_vertex
{
    int idx;
    int edge_value;
    int value;
    vertex* to_vertex;
};

class Graph
{
    vertex* vertexes;
    int size;

public:
    Graph(int n);
    int get_size();
    void addEdge(int i, int j, int key);
    void print_graph();
    void DFS(vertex* v, int value, bool* flag);
    bool is_correct();
};

Graph::Graph(int n)
{
    vertexes = new vertex[n];
    size = n;
}

int Graph::get_size()
{
    return this->size;
}

void Graph::addEdge(int i, int j, int key)
{

    adj_vertex tmp;
    tmp.idx = j;
    tmp.edge_value = key;
    tmp.to_vertex = &vertexes[j];

    vertexes[i].adj_list.push_back(tmp);
    vertexes[i].list_size++;

    tmp.idx = i;
    tmp.to_vertex = &vertexes[i];

    vertexes[j].adj_list.push_back(tmp);
    vertexes[j].list_size++;
}


void Graph::print_graph()
{
    cout << "\n print:" << endl;
    for (int i = 0; i < size; i++)
    {
        cout << "visited = " << vertexes[i].visited << "; i= " << i << ": ";
        int size = vertexes[i].adj_list.size();
        for (int j = 0; j < size; ++j)
        {
            cout << vertexes[i].adj_list[j].idx << " ";
        }
        cout << endl;
    }
}

void Graph::DFS(vertex* v, int value, bool* flag) //мб лучше не по указателю по индексу
{

    v->visited = true;
    v->label = value;

    vector<struct adj_vertex> adj_list
        = v->adj_list; // adj_list хранит список вершин, инцедентных v
    vertex* u;

    for (int i = 0; i < v->list_size; ++i)
    {
        if (flag)
        {
            u = adj_list[i].to_vertex;
            if (!u->visited)
            {
                int val = adj_list[i].edge_value - v->label;
                DFS(u, val, flag);
            }
            else
            {
                if (u->label + v->label != adj_list[i].edge_value)
                {
                    *flag = false;
                    break;
                }
            }
        }
        else
            break;
    }
}

bool Graph::is_correct()
{
    bool flag = true;
    for (int i = 0; i < this->size; ++i)
    {
        if (!vertexes[i].visited)
            DFS(&vertexes[i], 0, &flag);
        if (!flag)
            return false;
    }
    return true;
}


class FixedSet
{
    int count_numbers;
    int size;
    int a1, a2, b1, b2;
    vector<int> table;
    vector<int> A;

public:
    FixedSet();
    void Initialize(const vector<int>& numbers);
    bool Contains(int number) const;
    void print();
};

FixedSet::FixedSet()
{
    this->count_numbers = 0;
    this->size = 0;
}

void FixedSet::Initialize(const vector<int>& numbers)
{

    srand(4541);
    this->count_numbers = numbers.size(); //Число чисел для хранения
    this->size = (this->count_numbers) * c; //Размер графа

    int n = this->count_numbers;
    int m = this->size;
    this->table.resize(m);
    this->A.resize(m);

    int a, b;
    int alpha_k, beta_k;

    bool flag = true;
    while (flag)
    {
        Graph g(m);

        a1 = rand_int(1, p - 1);
        b1 = rand_int(0, p - 1);
        a2 = rand_int(1, p - 1);
        b2 = rand_int(0, p - 1);

        for (int i = 0; i < n; ++i)
        {
            alpha_k = uni_hash(a1, b1, m, numbers[i]);
            beta_k = uni_hash(a2, b2, m, numbers[i]);
            g.addEdge(alpha_k, beta_k, numbers[i]);
        }

        //Граф построен, осталось проверить что он корректный. Вызову DFS и он ответит yes or no

        if (g.is_correct())
        {
            flag = true;
            this->a1 = a1;
            this->a2 = a2;
            this->b1 = b1;
            this->b2 = b2;
        }
    }


    //Массив А заполнен, можно заполнить хэш таблицу используя построенную ХФ
    int idx;
    for (int i = 0; i < m; ++i)
    {
        idx = (A[uni_hash(a1, b1, m, numbers[i])] + A[uni_hash(a2, b2, m, numbers[i])]) % m;
        this->A[idx] = numbers[i];
    }
}

bool FixedSet::Contains(int number) const
{
    int m = this->size;
    int idx= (A[uni_hash(this->a1, this->b1, m, number)] + A[uni_hash(this->a2, this->b2, m, number)]) % m;

    if (0 <= idx < m)
        return (this->table[idx] == number);

    return false;
}

int main()
{
    FixedSet set;

    vector<int> a = {1,2,3};
    set.Initialize(a);
    cout << set.Contains(1) << endl;


    return 0;
}