vadimk772336

итог

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