Advertisement
Guest User

Untitled

a guest
Feb 9th, 2016
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.96 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.   std::uniform_int_distribution<int> distribution(lower_bound, upper_bound);
  59.   return distribution(generator);
  60. }
  61.  
  62. HashFunction GenerateRandomHashFunction(int prime, int modulo) {
  63.   const int multiplier_coeficient = GenerateRandomNumber(1, prime);
  64.   const int shift_coeficient = GenerateRandomNumber(0, prime);
  65.   return {multiplier_coeficient, shift_coeficient, prime, modulo};
  66. }
  67.  
  68. constexpr int kDefaultPrimeModulo = 2000000011;
  69.  
  70. class SecondLevelHashTable {
  71. public:
  72.   void Initialize(const std::vector<int>& numbers) {
  73.     if (numbers.empty()) {
  74.       return;
  75.     }
  76.     hash_function = GenerateHashFunctionWithoutCollisions(numbers);
  77.  
  78.     data.assign(numbers.size() * numbers.size(), kEmptyCell);
  79.     for (const int number : numbers) {
  80.       data[hash_function(number)] = number;
  81.     }
  82.   }
  83.  
  84.   bool Contains(const int number) const {
  85.     return !data.empty() && data[hash_function(number)] == number;
  86.   }
  87.  
  88. private:
  89.   std::vector<int> data;
  90.   HashFunction hash_function;
  91.   static constexpr int kEmptyCell = 2000000000;
  92.  
  93.   static bool HasCollisions(const HashFunction& possible_hash_function,
  94.                             const std::vector<int>& numbers) {
  95.     std::vector<bool> occupied(numbers.size() * numbers.size(), false);
  96.     for (const int number : numbers) {
  97.       const int hash = possible_hash_function(number);
  98.       if (!occupied[hash]) {
  99.         occupied[hash] = true;
  100.       } else {
  101.         return true;
  102.       }
  103.     }
  104.     return false;
  105.   }
  106.  
  107.   static HashFunction GenerateHashFunctionWithoutCollisions(
  108.       const std::vector<int>& numbers) {
  109.     HashFunction possible_hash_function;
  110.     do {
  111.       possible_hash_function = GenerateRandomHashFunction(kDefaultPrimeModulo,
  112.                                                           numbers.size() *
  113.                                                           numbers.size());
  114.     } while (HasCollisions(possible_hash_function, numbers));
  115.     return possible_hash_function;
  116.   }
  117. };
  118.  
  119. constexpr int SecondLevelHashTable::kEmptyCell;
  120.  
  121. std::vector<int> CalculateChainsSizes(const std::vector<int>& numbers,
  122.                                       const HashFunction& outer_hash_function) {
  123.   std::vector<int> chains_sizes(numbers.size(), 0);
  124.   for (const int number : numbers) {
  125.     const int hash = outer_hash_function(number);
  126.     ++chains_sizes[hash];
  127.   }
  128.   return chains_sizes;
  129. }
  130.  
  131. int64_t CalculateSumOfSquares(const std::vector<int>& numbers) {
  132.   int64_t sum_of_squares = 0;
  133.   for (const int item : numbers) {
  134.     sum_of_squares += static_cast<int64_t>(item) * item;
  135.   }
  136.   return sum_of_squares;
  137. }
  138.  
  139. class FixedSet {
  140. public:
  141.   void Initialize(const std::vector<int>& numbers) {
  142.     outer_hash_function = GenerateFittingHashFunction(numbers);
  143.     FillHashTables(numbers);
  144.   }
  145.  
  146.   bool Contains(int number) const {
  147.     const int hash = outer_hash_function(number);
  148.     return double_hash_table[hash].Contains(number);
  149.   }
  150.  
  151. private:
  152.   using Bucket = std::vector<int>;
  153.   std::vector<SecondLevelHashTable> double_hash_table;
  154.   HashFunction outer_hash_function;
  155.   static constexpr int kMaxSumOfSquaresRatio = 4;
  156.  
  157.   static bool HashFunctionFits(
  158.       const HashFunction& possible_outer_hash_function,
  159.       const std::vector<int>& numbers) {
  160.     const std::vector<int> chains_sizes = CalculateChainsSizes(numbers,
  161.                                                                possible_outer_hash_function);
  162.     return CalculateSumOfSquares(chains_sizes) <= kMaxSumOfSquaresRatio *
  163.                                                   numbers.size();
  164.   }
  165.  
  166.   static HashFunction GenerateFittingHashFunction(
  167.       const std::vector<int>& numbers) {
  168.     HashFunction possible_outer_hash_function;
  169.     do {
  170.       possible_outer_hash_function = GenerateRandomHashFunction(kDefaultPrimeModulo,
  171.                                                                 numbers.size());
  172.     } while (!HashFunctionFits(possible_outer_hash_function, numbers));
  173.     return possible_outer_hash_function;
  174.   }
  175.  
  176.   void FillDoubleHashTable(const std::vector<Bucket>& classes) {
  177.     double_hash_table.reserve(classes.size());
  178.     for (const Bucket& one_class : classes) {
  179.       SecondLevelHashTable inner_hash_table;
  180.       inner_hash_table.Initialize(one_class);
  181.       double_hash_table.push_back(inner_hash_table);
  182.     }
  183.   }
  184.  
  185.   void FillHashTables(const std::vector<int>& numbers) {
  186.     std::vector<Bucket> classes(numbers.size());
  187.     for (const int item : numbers) {
  188.       classes[outer_hash_function(item)].push_back(item);
  189.     }
  190.     FillDoubleHashTable(classes);
  191.   }
  192. };
  193.  
  194. constexpr int FixedSet::kMaxSumOfSquaresRatio;
  195.  
  196. FixedSet BuildFixedSetFromInput(std::istream& in_stream = std::cin) {
  197.   const std::vector<int> numbers = ReadSetElements(in_stream);
  198.   FixedSet fixed_set;
  199.   fixed_set.Initialize(numbers);
  200.   return fixed_set;
  201. }
  202.  
  203. std::vector<bool> AnswerQueries(const FixedSet& fixed_set,
  204.                                 const std::vector<int>& queries) {
  205.   std::vector<bool> answers;
  206.   answers.reserve(queries.size());
  207.     for (const int query : queries) {
  208.       answers.push_back(fixed_set.Contains(query));
  209.     }
  210.   return answers;
  211. }
  212.  
  213.  
  214. void WriteAnswers(const std::vector<bool>& answers,
  215.                   std::ostream& out_stream = std::cout) {
  216.   for (const bool answer : answers) {
  217.     out_stream << (answer ? "Yes" : "No") << '\n';
  218.   }
  219. }
  220.  
  221. int main() {
  222.   std::ios_base::sync_with_stdio(false);
  223.   std::cin.tie(nullptr);
  224.  
  225.   const FixedSet fixed_set = BuildFixedSetFromInput();
  226.   const std::vector<int> queries = ReadQueries();
  227.   const std::vector<bool> answers = AnswerQueries(fixed_set, queries);
  228.   WriteAnswers(answers);
  229.   return 0;
  230. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement