vadimk772336

Ивану

Nov 25th, 2021 (edited)
463
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <stdexcept>
  4. #include <cstring>
  5. #include <random>
  6. #include <utility>
  7. #include <ctime>
  8.  
  9. int rand()
  10. { // NOLINT
  11.     throw std::runtime_error("Don't use rand");
  12. }
  13.  
  14. const int p = 2000000033;
  15. const int shift = 1e9 // Чтобы все ключи были неотрицательные
  16.     const int c
  17.     = 3;
  18.  
  19. std::random_device rand_dev;
  20. std::mt19937 generator(rand_dev());
  21.  
  22. int rand_int(int min, int max)
  23. {
  24.     std::uniform_int_distribution<int> distr(min, max);
  25.     return distr(generator);
  26. }
  27.  
  28. long long int uni_hash(long long int a, long long int b, int m, int key)
  29. {
  30.     return ((a * key + b) % p) % m;
  31. }
  32.  
  33. struct vertex
  34. {
  35.     bool visited = false;
  36.     std::vector<struct adj_vertex> adj_list;
  37.     int list_size = 0;
  38.     long long int label = -1;
  39. };
  40.  
  41. struct adj_vertex
  42. {
  43.     int idx;
  44.     int edge_value;
  45. };
  46.  
  47. class Graph
  48. {
  49.     vertex* G;
  50.     int size;
  51.  
  52. public:
  53.     Graph(int n);
  54.     int get_size();
  55.     void addEdge(int i, int j, int key_idx);
  56.     void DFS(int v_idx, int value, bool& flag);
  57.     bool is_correct();
  58.     long long int get_label(int number_vertex);
  59. };
  60.  
  61. Graph::Graph(int n)
  62. {
  63.     G = new vertex[n];
  64.     size = n;
  65. }
  66.  
  67. long long int Graph::get_label(int number_vertex)
  68. {
  69.     return G[number_vertex].label;
  70. }
  71.  
  72. int Graph::get_size()
  73. {
  74.     return this->size;
  75. }
  76.  
  77. void Graph::addEdge(int i, int j, int key_idx)
  78. {
  79.     adj_vertex tmp;
  80.     tmp.idx = j;
  81.     tmp.edge_value = key_idx;
  82.  
  83.     G[i].adj_list.push_back(tmp);
  84.  
  85.     tmp.idx = i;
  86.     G[j].adj_list.push_back(tmp);
  87.  
  88.     G[i].list_size++;
  89.     G[j].list_size++;
  90. }
  91.  
  92. void Graph::DFS(int v_idx, int value, bool& flag)
  93. {
  94.  
  95.     if (flag)
  96.     {
  97.         G[v_idx].visited = true;
  98.         G[v_idx].label = value;
  99.  
  100.         vertex u;
  101.         std::vector<struct adj_vertex> curr_list = G[v_idx].adj_list;
  102.         int u_idx, val, edge_value;
  103.  
  104.         for (int i = 0; i < G[v_idx].list_size; ++i)
  105.         {
  106.  
  107.             u_idx = curr_list[i].idx;
  108.             u = G[u_idx];
  109.             edge_value = curr_list[i].edge_value;
  110.  
  111.             if (!(u.visited))
  112.             {
  113.                 val = edge_value - value;
  114.                 DFS(u_idx, val, flag);
  115.             }
  116.  
  117.             if (((G[u_idx].label + G[v_idx].label) % (this->size)) != edge_value)
  118.             {
  119.                 flag = false;
  120.                 break;
  121.             }
  122.         }
  123.     }
  124. }
  125.  
  126.  
  127. bool Graph::is_correct()
  128. {
  129.  
  130.     bool flag = true;
  131.     for (int i = 0; i < this->size; ++i)
  132.     {
  133.         if (!G[i].visited)
  134.             DFS(i, 0, flag);
  135.         if (!flag)
  136.             return false;
  137.     }
  138.     return true;
  139. }
  140.  
  141. class FixedSet
  142. {
  143.     int count_numbers;
  144.     int size;
  145.     long long int alpha_a, alpha_b, beta_a, beta_b;
  146.     std::vector<int> table;
  147.     std::vector<int> A;
  148.  
  149. public:
  150.     FixedSet();
  151.     void Initialize(const std::vector<int>& numbers);
  152.     bool Contains(int number) const;
  153. };
  154.  
  155. FixedSet::FixedSet()
  156. {
  157.     this->count_numbers = 0;
  158.     this->size = 0;
  159. }
  160.  
  161. void FixedSet::Initialize(const std::vector<int>& numbers)
  162. {
  163.  
  164.     this->count_numbers = numbers.size();
  165.     this->size = (this->count_numbers) * c;
  166.  
  167.     int n = this->count_numbers;
  168.     int m = this->size;
  169.     this->A.resize(m);
  170.  
  171.     for (int i = 0; i < n; ++i)
  172.         table.push_back(numbers[i] + shift);
  173.  
  174.     long long int alpha_k, beta_k;
  175.     bool flag = false;
  176.  
  177.     while (!flag)
  178.     {
  179.         Graph g(m);
  180.  
  181.         this->alpha_a = rand_int(1, p - 1);
  182.         this->alpha_b = rand_int(0, p - 1);
  183.         this->beta_a = rand_int(1, p - 1);
  184.         this->beta_b = rand_int(0, p - 1);
  185.  
  186.         for (int i = 0; i < n; ++i)
  187.         {
  188.             alpha_k = uni_hash(alpha_a, alpha_b, m, numbers[i]);
  189.             beta_k = uni_hash(beta_a, beta_b, m, numbers[i]);
  190.             g.addEdge(alpha_k, beta_k, i);
  191.         }
  192.  
  193.         if (g.is_correct())
  194.         {
  195.             flag = true;
  196.             for (int i = 0; i < m; ++i)
  197.                 this->A[i] = g.get_label(i);
  198.         }
  199.     }
  200. }
  201.  
  202. bool FixedSet::Contains(int number) const
  203. {
  204.     int m = this->size;
  205.     int hash1 = uni_hash(this->alpha_a, this->alpha_b, m, number + shift);
  206.     int hash2 = uni_hash(this->beta_a, this->beta_b, m, number + shift);
  207.  
  208.     int idx = (A[hash1] + A[hash2]) % m;
  209.  
  210.     if (0 <= idx < m)
  211.         return (this->table[idx] == number + shift);
  212.  
  213.     return false;
  214. }
  215.  
  216. std::vector<int> ReadSequence()
  217. {
  218.     size_t size;
  219.     std::cin >> size;
  220.     std::vector<int> sequence(size);
  221.     for (auto& current : sequence)
  222.     {
  223.         std::cin >> current;
  224.     }
  225.     return sequence;
  226. }
  227.  
  228. std::vector<bool> PerformRequests(const std::vector<int>& requests, const FixedSet& set)
  229. {
  230.     std::vector<bool> request_answers;
  231.     request_answers.reserve(requests.size());
  232.     for (int request : requests)
  233.     {
  234.         request_answers.push_back(set.Contains(request));
  235.     }
  236.     return request_answers;
  237. }
  238.  
  239. void PrintRequestsResponse(const std::vector<bool>& request_answers)
  240. {
  241.     for (bool answer : request_answers)
  242.     {
  243.         std::cout << (answer ? "Yes" : "No") << "\n";
  244.     }
  245. }
  246.  
  247. void RunTests();
  248.  
  249. int main(int argc, char** argv)
  250. {
  251.     std::ios::sync_with_stdio(false);
  252.     auto numbers = ReadSequence();
  253.     auto requests = ReadSequence();
  254.     FixedSet set;
  255.     set.Initialize(numbers);
  256.     PrintRequestsResponse(PerformRequests(requests, set));
  257.  
  258.     return 0;
  259. }
  260.  
RAW Paste Data