Advertisement
Guest User

Untitled

a guest
Feb 8th, 2016
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <string>
  5. #include <math.h>
  6. #include <algorithm>
  7. #include <map>
  8. #include <set>
  9. #include <stack>
  10. #include <functional>
  11. #include <list>
  12. #include <ctime>
  13.  
  14. std::vector<int> ReadSetElements(std::istream& in_stream = std::cin) {
  15.   int quantity;
  16.   in_stream >> quantity;
  17.   std::vector<int> numbers(quantity);
  18.   for (int& number : numbers) {
  19.     in_stream >> number;
  20.   }
  21.   return numbers;
  22. }
  23.  
  24. std::vector<int> ReadQueries(std::istream& in_stream = std::cin) {
  25.   int quantity;
  26.   in_stream >> quantity;
  27.   std::vector<int> queries(quantity);
  28.   for (int& query : queries) {
  29.     in_stream >> query;
  30.   }
  31.   return queries;
  32. }
  33.  
  34. class HashFunction {
  35.   int multiplier;
  36.   int shift;
  37.   int prime;
  38.   int modulo;
  39.  
  40. public:
  41.   HashFunction() = default;
  42.  
  43.   HashFunction(int new_multiplier, int new_shift, int new_prime, int new_modulo)
  44.       : multiplier(new_multiplier), shift(new_shift), prime(new_prime),
  45.         modulo(new_modulo) {}
  46.  
  47.   int operator()(int number) const {
  48.     int hash_function_value = (static_cast<int64_t>(multiplier) * number + shift) % prime;
  49.     if (hash_function_value < 0) {
  50.       hash_function_value += prime;
  51.     }
  52.     return hash_function_value % modulo;
  53.   }
  54. };
  55.  
  56. int GenerateRandomNumber(int lower_bound, int upper_bound) {
  57.   static std::default_random_engine generator;
  58.   static std::uniform_int_distribution<int> distribution(lower_bound,
  59.                                                          upper_bound);
  60.   return distribution(generator);
  61. }
  62.  
  63. HashFunction GenerateRandomHashFunction(int prime, int modulo) {
  64.   const int multiplier_coeficient = GenerateRandomNumber(1, prime);
  65.   const int shift_coeficient = GenerateRandomNumber(0, prime);
  66.   return {multiplier_coeficient, shift_coeficient, prime, modulo};
  67. }
  68.  
  69. constexpr int kDefaultPrimeModulo = 2000000011;
  70.  
  71. class SecondLevelHashTable {
  72. public:
  73.   void Initialize(const std::vector<int>& numbers) {
  74.     if (numbers.empty()) {
  75.       return;
  76.     }
  77.     hash_function = GenerateHashFunctionWithoutCollisions(numbers);
  78.  
  79.     data.assign(numbers.size() * numbers.size(), kEmptyCell);
  80.     for (const int number : numbers) {
  81.       data[hash_function(number)] = number;
  82.     }
  83.   }
  84.  
  85.   bool Contains(const int number) const {
  86.     return !data.empty() && data[hash_function(number)] == number;
  87.   }
  88.  
  89. private:
  90.   std::vector<int> data;
  91.   HashFunction hash_function;
  92.   static constexpr int kEmptyCell = 2000000000;
  93.  
  94.   static HashFunction GenerateHashFunctionWithoutCollisions(
  95.       const std::vector<int>& numbers) {
  96.     HashFunction possible_hash_function;
  97.     bool has_collisions = true;
  98.     do {
  99.       std::vector<int> table(numbers.size() * numbers.size(), kEmptyCell);
  100.       possible_hash_function = GenerateRandomHashFunction(kDefaultPrimeModulo,
  101.                                                           numbers.size() *
  102.                                                           numbers.size());
  103.       has_collisions = false;
  104.       for (const int number : numbers) {
  105.         const int hash = possible_hash_function(number);
  106.         if (table[hash] == kEmptyCell) {
  107.           table[hash] = number;
  108.         } else if (table[hash] != number) {
  109.           has_collisions = true;
  110.         }
  111.       }
  112.     } while (has_collisions);
  113.     return possible_hash_function;
  114.   }
  115. };
  116.  
  117. constexpr int SecondLevelHashTable::kEmptyCell;
  118.  
  119. std::vector<int> CalculateChainsSizes(const std::vector<int>& numbers,
  120.                                       const HashFunction& outer_hash_function) {
  121.   std::vector<int> chains_sizes(numbers.size(), 0);
  122.   for (const int number : numbers) {
  123.     const int hash = outer_hash_function(number);
  124.     ++chains_sizes[hash];
  125.   }
  126.   return chains_sizes;
  127. }
  128.  
  129. int64_t CalculateSumOfSquares(const std::vector<int>& numbers) {
  130.   int64_t sum_of_squares = 0;
  131.   for (const int item : numbers) {
  132.     sum_of_squares += static_cast<int64_t>(item) * item;
  133.   }
  134.   return sum_of_squares;
  135. }
  136.  
  137. class FixedSet {
  138. public:
  139.   void Initialize(const std::vector<int>& numbers) {
  140.     outer_hash_function = GenerateFittingHashFunction(numbers);
  141.     FillHashTables(numbers);
  142.   }
  143.  
  144.   bool Contains(int number) const {
  145.     const int hash = outer_hash_function(number);
  146.     return double_hash_table[hash].Contains(number);
  147.   }
  148.  
  149. private:
  150.   using Bucket = std::vector<int>;
  151.   std::vector<SecondLevelHashTable> double_hash_table;
  152.   HashFunction outer_hash_function;
  153.   static constexpr int kMaxSumOfSquaresRatio = 4;
  154.  
  155.   static bool HashFunctionFits(
  156.       const HashFunction& possible_outer_hash_function,
  157.       const std::vector<int>& numbers) {
  158.     std::vector<int> chains_sizes = CalculateChainsSizes(numbers,
  159.                                                          possible_outer_hash_function);
  160.     return CalculateSumOfSquares(chains_sizes) <= kMaxSumOfSquaresRatio * numbers.size();
  161.   }
  162.  
  163.   static HashFunction GenerateFittingHashFunction(
  164.       const std::vector<int>& numbers) {
  165.     HashFunction possible_outer_hash_function;
  166.     do {
  167.       possible_outer_hash_function = GenerateRandomHashFunction(kDefaultPrimeModulo,
  168.                                                                 numbers.size());
  169.       } while (!HashFunctionFits(possible_outer_hash_function, numbers));
  170.     return possible_outer_hash_function;
  171.   }
  172.  
  173.   void FillDoubleHashTable(const std::vector<Bucket>& classes) {
  174.     double_hash_table.reserve(classes.size());
  175.     for (const Bucket& one_class : classes) {
  176.       SecondLevelHashTable inner_hash_table;
  177.       inner_hash_table.Initialize(one_class);
  178.       double_hash_table.push_back(inner_hash_table);
  179.     }
  180.   }
  181.  
  182.   void FillHashTables(const std::vector<int>& numbers) {
  183.     std::vector<Bucket> classes(numbers.size());
  184.     for (const int item : numbers) {
  185.       classes[outer_hash_function(item)].push_back(item);
  186.     }
  187.     FillDoubleHashTable(classes);
  188.   }
  189. };
  190.  
  191. FixedSet BuildFixedSetFromInput(std::istream& in_stream = std::cin) {
  192.   const std::vector<int> numbers = ReadSetElements(in_stream);
  193.   FixedSet fixed_set;
  194.   fixed_set.Initialize(numbers);
  195.   return fixed_set;
  196. }
  197.  
  198. std::vector<bool> AnswerQueries(const FixedSet& fixed_set,
  199.                                 const std::vector<int>& queries) {
  200.   std::vector<bool> answers;
  201.   answers.reserve(queries.size());
  202.     for (const int query : queries) {
  203.       answers.push_back(fixed_set.Contains(query));
  204.     }
  205.   return answers;
  206. }
  207.  
  208.  
  209. void WriteAnswers(const std::vector<bool>& answers,
  210.                   std::ostream& out_stream = std::cout) {
  211.   for (const bool answer : answers) {
  212.     out_stream << (answer ? "Yes" : "No") << '\n';
  213.   }
  214. }
  215.  
  216. int main() {
  217.   std::ios_base::sync_with_stdio(false);
  218.   std::cin.tie(nullptr);
  219.  
  220.   const FixedSet fixed_set = BuildFixedSetFromInput();
  221.   const std::vector<int> queries = ReadQueries();
  222.   const std::vector<bool> answers = AnswerQueries(fixed_set, queries);
  223.   WriteAnswers(answers);
  224.   return 0;
  225. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement