vadimk772336

CE 84

Nov 25th, 2021
457
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.     explicit 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 buff;
  79.     buff.idx = j;
  80.     buff.edge_value = key_idx;
  81.  
  82.     G[i].adj_list.push_back(buff);
  83.  
  84.     buff.idx = i;
  85.     G[j].adj_list.push_back(buff);
  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.     table.clear();
  163.     A.clear();
  164.  
  165.     if (!numbers.empty())
  166.     {
  167.         this->count_numbers = numbers.size();
  168.         this->size = (this->count_numbers) * c;
  169.  
  170.         int n = this->count_numbers;
  171.         int m = this->size;
  172.         this->A.resize(m);
  173.  
  174.         for (int i = 0; i < n; ++i)
  175.             table.push_back(numbers[i] + shift);
  176.  
  177.         long long int alpha_k, beta_k;
  178.         bool flag = false;
  179.  
  180.         while (!flag)
  181.         {
  182.             Graph g(m);
  183.  
  184.             this->alpha_a = rand_int(1, p - 1);
  185.             this->alpha_b = rand_int(0, p - 1);
  186.             this->beta_a = rand_int(1, p - 1);
  187.             this->beta_b = rand_int(0, p - 1);
  188.  
  189.             for (int i = 0; i < n; ++i)
  190.             {
  191.                 alpha_k = uni_hash(alpha_a, alpha_b, m, numbers[i] + shift);
  192.                 beta_k = uni_hash(beta_a, beta_b, m, numbers[i] + shift);
  193.                 g.addEdge(alpha_k, beta_k, i);
  194.             }
  195.  
  196.             if (g.is_correct())
  197.             {
  198.                 flag = true;
  199.                 for (int i = 0; i < m; ++i)
  200.                     this->A[i] = g.get_label(i);
  201.             }
  202.         }
  203.     }
  204. }
  205.  
  206. bool FixedSet::Contains(int number) const
  207. {
  208.     if (this->size == 0)
  209.         return false;
  210.  
  211.     int m = this->size;
  212.     int hash_alpha = uni_hash(this->alpha_a, this->alpha_b, m, number + shift);
  213.     int hash_beta = uni_hash(this->beta_a, this->beta_b, m, number + shift);
  214.  
  215.     int idx = (A[hash_alpha] + A[hash_beta]) % m;
  216.  
  217.     if (0 <= idx < m)
  218.         return (this->table[idx] == number + shift);
  219.  
  220.     return false;
  221. }
  222.  
  223. std::vector<int> ReadSequence()
  224. {
  225.     size_t size;
  226.     std::cin >> size;
  227.     std::vector<int> sequence(size);
  228.     for (auto& current : sequence)
  229.     {
  230.         std::cin >> current;
  231.     }
  232.     return sequence;
  233. }
  234.  
  235. std::vector<bool> PerformRequests(const std::vector<int>& requests, const FixedSet& set)
  236. {
  237.     std::vector<bool> request_answers;
  238.     request_answers.reserve(requests.size());
  239.     for (int request : requests)
  240.     {
  241.         request_answers.push_back(set.Contains(request));
  242.     }
  243.     return request_answers;
  244. }
  245.  
  246. void PrintRequestsResponse(const std::vector<bool>& request_answers)
  247. {
  248.     for (bool answer : request_answers)
  249.     {
  250.         std::cout << (answer ? "Yes" : "No") << "\n";
  251.     }
  252. }
  253.  
  254. int main(int argc, char** argv)
  255. {
  256.  
  257.     std::ios::sync_with_stdio(false);
  258.     auto numbers = ReadSequence();
  259.     auto requests = ReadSequence();
  260.     FixedSet set;
  261.     set.Initialize(numbers);
  262.     PrintRequestsResponse(PerformRequests(requests, set));
  263.  
  264.     return 0;
  265. }
  266.  
RAW Paste Data