vadimk772336

работает типо

Nov 25th, 2021
501
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdlib> // для функций rand() и srand()
  4. #include <list>
  5. #include <random>
  6. #include <ctime>
  7. using namespace std;
  8.  
  9. const int p = 2 * 1e9 + 11;
  10. const int c = 3;
  11.  
  12. std::random_device rand_dev;
  13. std::mt19937 generator(rand_dev());
  14.  
  15. int rand_int(int min, int max)
  16. {
  17.     std::uniform_int_distribution<int> distr(min, max);
  18.     return distr(generator);
  19. }
  20.  
  21. long long int uni_hash(long long int a, long long int b, int m, int key)
  22. {
  23.     return ((a * key + b) % p) % m;
  24. }
  25.  
  26. struct vertex
  27. {
  28.     bool visited = false;
  29.     vector<struct adj_vertex> adj_list;
  30.     int list_size = 0;
  31.     long long int label = -1;
  32. };
  33.  
  34. struct adj_vertex
  35. {
  36.     int idx;
  37.     int edge_value;
  38. };
  39.  
  40. class Graph
  41. {
  42.     vertex* G;
  43.     int size;
  44.  
  45. public:
  46.     Graph(int n);
  47.     int get_size();
  48.     void addEdge(int i, int j, int key_idx);
  49.     void print_graph();
  50.     void DFS(int v_idx, int value, bool& flag);
  51.     bool is_correct();
  52.     long long int get_label(int number_vertex);
  53. };
  54.  
  55. Graph::Graph(int n)
  56. {
  57.     G = new vertex[n];
  58.     size = n;
  59. }
  60.  
  61. long long int Graph::get_label(int number_vertex)
  62. {
  63.     return G[number_vertex].label;
  64. }
  65.  
  66. int Graph::get_size()
  67. {
  68.     return this->size;
  69. }
  70.  
  71. void Graph::addEdge(int i, int j, int key_idx)
  72. {
  73.  
  74.     if (i < 0 || j < 0)
  75.     {
  76.         cout << "Передана вершина с отриц. индексом - ошибка! \n";
  77.     }
  78.    
  79.     //cout << "addEdge by :" << i << " " << j << " " << key_idx << endl;
  80.    
  81.     adj_vertex tmp;
  82.     tmp.idx = j;
  83.     tmp.edge_value = key_idx;
  84.  
  85.     G[i].adj_list.push_back(tmp);
  86.  
  87.     tmp.idx = i;
  88.     G[j].adj_list.push_back(tmp);
  89.  
  90.     G[i].list_size++;
  91.     G[j].list_size++;
  92.    
  93.  
  94.    
  95. }
  96.  
  97.  
  98. void Graph::print_graph()
  99. {
  100.     cout << "\n print:" << endl;
  101.     for (int i = 0; i < size; i++)
  102.     {
  103.         cout << "visited = " << G[i].visited << "; i= " << i << "; ";
  104.         cout << " label = " << G[i].label << " : ";
  105.         int size = G[i].adj_list.size();
  106.  
  107.         cout << "idx =: ";
  108.         for (int j = 0; j < size; ++j)
  109.         {
  110.             cout << G[i].adj_list[j].idx << " ";
  111.         }
  112.  
  113.  
  114.         cout << ";   edge_value =: ";
  115.         for (int j = 0; j < size; ++j)
  116.         {
  117.             cout << G[i].adj_list[j].edge_value << " ";
  118.         }
  119.         cout << endl;
  120.     }
  121. }
  122.  
  123. void Graph::DFS(int v_idx, int value, bool& flag) //мб лучше не по указателю по индексу
  124. {
  125.  
  126.     if (flag)
  127.     {
  128.         G[v_idx].visited = true;
  129.         G[v_idx].label = value;
  130.  
  131.         vertex u;
  132.         vector<struct adj_vertex> curr_list = G[v_idx].adj_list;
  133.         int u_idx, val, edge_value;
  134.  
  135.         for (int i = 0; i < G[v_idx].list_size; ++i)
  136.         {
  137.  
  138.             u_idx = curr_list[i].idx;
  139.             u = G[u_idx];
  140.             edge_value = curr_list[i].edge_value;
  141.  
  142.             if (!(u.visited))
  143.             {
  144.                 val = edge_value - value;
  145.                 DFS(u_idx, val, flag);
  146.             }
  147.  
  148.             if ( ( (G[u_idx].label + G[v_idx].label) % (this->size) )  != edge_value)
  149.             {
  150.                 flag = false;
  151.             }
  152.         }
  153.     }
  154. }
  155.  
  156.  
  157. bool Graph::is_correct()
  158. {
  159.  
  160.     bool flag = true;
  161.     for (int i = 0; i < this->size; ++i)
  162.     {
  163.         if (!G[i].visited)
  164.             DFS(i, 0, flag);
  165.         if (!flag)
  166.             return false;
  167.     }
  168.     return true;
  169. }
  170.  
  171. class FixedSet
  172. {
  173.     int count_numbers;
  174.     int size;
  175.     long long int a1, a2, b1, b2;
  176.     vector<int> table;
  177.     vector<int> A;
  178.  
  179. public:
  180.     FixedSet();
  181.     void Initialize(const vector<int>& numbers);
  182.     bool Contains(int number) const;
  183.     void print();
  184. };
  185.  
  186.  
  187. FixedSet::FixedSet()
  188. {
  189.     this->count_numbers = 0;
  190.     this->size = 0;
  191. }
  192.  
  193. void FixedSet::Initialize(const vector<int>& numbers)
  194. {
  195.  
  196.  
  197.     this->count_numbers = numbers.size(); //Число чисел для хранения
  198.     this->size = (this->count_numbers) * c; //Размер графа
  199.  
  200.     int n = this->count_numbers;
  201.     int m = this->size;
  202.    
  203.     for (int i =0; i < n; ++i)
  204.         table.push_back(numbers[i]);
  205.    
  206.     cout << "n,m,p = " << n << " " << m  << " " << p << endl;
  207.    
  208.     this->table.resize(m);
  209.     this->A.resize(m);
  210.  
  211.     int a, b;
  212.     long long int alpha_k, beta_k;
  213.  
  214.     bool flag = false;
  215.    
  216.     cout << "Сейчас зайду в вайл" << endl;
  217.     while (!flag)
  218.     {
  219.         cout << "Зашёл" << endl;
  220.         Graph g(m);
  221.  
  222.         a1 = rand_int(1, p - 1);
  223.         b1 = rand_int(0, p - 1);
  224.         a2 = rand_int(1, p - 1);
  225.         b2 = rand_int(0, p - 1);
  226.         cout << "Сгенерил а б а б  " << a1 << " " << b1 << " " << a2 << " " << b1 << endl;
  227.        
  228.         for (int i = 0; i < n; ++i)
  229.         {
  230.             alpha_k = uni_hash(a1, b1, m, numbers[i]);
  231.             beta_k = uni_hash(a2, b2, m, numbers[i]);
  232.            
  233.             cout << "i: " << i << " alpha_k, beta_k : " << alpha_k << " " << beta_k << endl;
  234.             g.addEdge(alpha_k, beta_k, i);
  235.         }
  236.  
  237.         //Граф построен, осталось проверить что он корректный. Вызову DFS и он ответит yes or no
  238.         cout << "Граф построен, осталось проверить что он корректный" << endl;
  239.         //g.print_graph();
  240.        
  241.         if (g.is_correct())
  242.         {
  243.             cout << "correct!" << endl;
  244.             flag = true;
  245.             this->a1 = a1;
  246.             this->a2 = a2;
  247.             this->b1 = b1;
  248.             this->b2 = b2;
  249.             g.print_graph();
  250.            
  251.             cout << "\n запишу А" << endl;
  252.            
  253.             for (int i = 0; i < m; ++i)
  254.             {
  255.                 this->A[i] = g.get_label(i);
  256.                 //cout << "A[" << i << "] = " << this->A[i] << "; ";
  257.             }
  258.         }
  259.     }
  260. }
  261.  
  262. bool FixedSet::Contains(int number) const
  263. {
  264.     int m = this->size;
  265.     int hash1 = uni_hash(this->a1, this->b1, m, number);
  266.     int hash2 = uni_hash(this->a2, this->b2, m, number);
  267.    
  268.     int idx = (A[hash1] + A[hash2]) % m;
  269.  
  270.     if (0 <= idx < m)
  271.         return (this->table[idx] == number);
  272.  
  273.     return false;
  274. }
  275.  
  276. int main()
  277. {
  278.     FixedSet Fix_set;
  279.     std::vector<int> F;
  280.     long long int req;
  281.     int a, n, count_of_req;
  282.     std::cin >> n;
  283.     for (int i = 0; i < n; ++i)
  284.     {
  285.         std::cin >> a;
  286.         F.push_back(a);
  287.     }
  288.     std::cin >> count_of_req;
  289.  
  290.     Fix_set.Initialize(F);
  291.     for (int i = 0; i < count_of_req; ++i)
  292.     {
  293.         std::cin >> req;
  294.         if (Fix_set.Contains(req))
  295.             std::cout << "Yes" << std::endl;
  296.         else
  297.             std::cout << "No" << std::endl;
  298.     }
  299.     return 0;
  300. }
  301.  
RAW Paste Data