Advertisement
Guest User

Untitled

a guest
Nov 20th, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.72 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <random>
  4. #include <utility>
  5. #include <vector>
  6. using std::vector;
  7.  
  8. class HashFunction;
  9. class FixedSet;
  10. std::pair<vector<long long>, vector<long long>> ReadInput();
  11. vector<bool> Solve(std::pair<vector<long long>, vector<long long>> input);
  12. void Print(const vector<bool>& answer);
  13.  
  14. class HashFunction {
  15.  public:
  16.   void InitializeRandomly(long long mod, std::mt19937* generator);
  17.   long long Count(long long input) const;
  18.  
  19.  private:
  20.   long long multiplier, adder;
  21.   long long module = 1;
  22.   long long prime = 2000000011;
  23. };
  24.  
  25. class FixedSet {
  26.  public:
  27.   FixedSet() {}
  28.   void Initialize(const vector<long long>& data);
  29.   bool Contains(long long number) const;
  30.  
  31.  private:
  32.   vector<vector<long long>> hash_table;
  33.   HashFunction upper_hash;
  34.   vector<HashFunction> list_of_down_hashes;
  35.   long long quantity_of_buckets = 0;
  36.   long long not_in_set = 2000000000;
  37.   const int upper_level = 1;
  38.   const int down_level = -1;
  39.   bool IsOkHashFunction(int level, HashFunction hash,
  40.                         const vector<long long>& data);
  41.   HashFunction ChoosePerfectHash(const vector<long long>& data,
  42.                                  std::mt19937* generator);
  43.   vector<long long> BucketsOfPerfectHash(HashFunction hash,
  44.                                          long long number_of_buckets,
  45.                                          const vector<long long>& data);
  46.  
  47.   HashFunction ChooseUpperHash(const vector<long long> keys,
  48.                                std::mt19937* generator);
  49.   vector<vector<long long>> BucketsOfUpperHash(HashFunction hash,
  50.                                                const vector<long long>& data);
  51. };
  52.  
  53. void HashFunction::InitializeRandomly(long long mod, std::mt19937* generator) {
  54.   std::uniform_int_distribution<> dis(0, prime);
  55.   multiplier = dis(*generator);
  56.   adder = dis(*generator);
  57.   if (mod > 0) {
  58.     module = mod;
  59.   }
  60. }
  61.  
  62. long long HashFunction::Count(long long input) const {
  63.   return ((multiplier * ((input + prime) % prime) + adder) % prime) % module;
  64. }
  65.  
  66. void FixedSet::Initialize(const vector<long long>& data) {
  67.   std::random_device random;
  68.   std::mt19937 gen(random());
  69.   vector<vector<long long>> list_of_buckets;
  70.   quantity_of_buckets = data.size();
  71.   upper_hash = ChooseUpperHash(data, &gen);
  72.   list_of_buckets = BucketsOfUpperHash(upper_hash, data);
  73.   for (int bucket_number = 0; bucket_number < quantity_of_buckets;
  74.        ++bucket_number) {
  75.     HashFunction current_hash =
  76.         ChoosePerfectHash(list_of_buckets[bucket_number], &gen);
  77.     list_of_down_hashes.push_back(current_hash);
  78.     long long current_bucket_size_squared =
  79.         list_of_buckets[bucket_number].size() *
  80.         list_of_buckets[bucket_number].size();
  81.     hash_table.push_back(BucketsOfPerfectHash(current_hash,
  82.                                               current_bucket_size_squared,
  83.                                               list_of_buckets[bucket_number]));
  84.   }
  85. }
  86.  
  87. bool FixedSet::Contains(long long number) const {
  88.   if (quantity_of_buckets == 0) {
  89.     return false;
  90.   }
  91.   HashFunction down_hash = list_of_down_hashes[upper_hash.Count(number)];
  92.   return hash_table[upper_hash.Count(number)][down_hash.Count(number)] ==
  93.          number;
  94. }
  95.  
  96. bool FixedSet::IsOkHashFunction(int level, HashFunction hash,
  97.                                 const vector<long long>& data) {
  98.   if (level == upper_level) {
  99.     vector<int> sizes_of_buckets(data.size());
  100.     size_t sum_of_squares_of_sizes = 0;
  101.     for (auto key : data) {
  102.       sizes_of_buckets[hash.Count(key)] += 1;
  103.     }
  104.     for (auto size : sizes_of_buckets) {
  105.       sum_of_squares_of_sizes += size * size;
  106.     }
  107.     return sum_of_squares_of_sizes <= 4 * data.size();
  108.  
  109.   } else {
  110.     for (size_t left = 0; left < data.size(); ++left) {
  111.       for (size_t right = left + 1; right < data.size(); ++right) {
  112.         if (hash.Count(data[left]) == hash.Count(data[right])) {
  113.           return false;
  114.         }
  115.       }
  116.     }
  117.   }
  118.   return true;
  119. }
  120.  
  121. HashFunction FixedSet::ChoosePerfectHash(const vector<long long>& data,
  122.                                          std::mt19937* generator) {
  123.   HashFunction perfect_hash;
  124.   perfect_hash.InitializeRandomly(data.size() * data.size(), generator);
  125.   while (not IsOkHashFunction(down_level, perfect_hash, data)) {
  126.     perfect_hash.InitializeRandomly(data.size() * data.size(), generator);
  127.   }
  128.   return perfect_hash;
  129. }
  130.  
  131. vector<long long> FixedSet::BucketsOfPerfectHash(
  132.     HashFunction hash, long long number_of_buckets,
  133.     const vector<long long>& data) {
  134.   vector<long long> answer(number_of_buckets + 1, not_in_set);
  135.   for (auto key : data) {
  136.     answer[hash.Count(key)] = key;
  137.   }
  138.   return answer;
  139. }
  140.  
  141. HashFunction FixedSet::ChooseUpperHash(const vector<long long> keys,
  142.                                        std::mt19937* generator) {
  143.   HashFunction desired_hash;
  144.   desired_hash.InitializeRandomly(quantity_of_buckets, generator);
  145.   while (not IsOkHashFunction(upper_level, desired_hash, keys)) {
  146.     desired_hash.InitializeRandomly(quantity_of_buckets, generator);
  147.   }
  148.   return desired_hash;
  149. }
  150.  
  151. vector<vector<long long>> FixedSet::BucketsOfUpperHash(
  152.     HashFunction hash, const vector<long long>& data) {
  153.   vector<vector<long long>> answer(data.size(), vector<long long>());
  154.   for (auto key : data) {
  155.     answer[hash.Count(key)].push_back(key);
  156.   }
  157.   return answer;
  158. }
  159.  
  160. std::pair<vector<long long>, vector<long long>> ReadInput() {
  161.   vector<long long> keys;
  162.   vector<long long> queries;
  163.   int size_of_set;
  164.   std::cin >> size_of_set;
  165.   for (int pos = 0; pos < size_of_set; ++pos) {
  166.     long long key;
  167.     std::cin >> key;
  168.     keys.push_back(key);
  169.   }
  170.   int number_of_queries;
  171.   std::cin >> number_of_queries;
  172.   for (int pos = 0; pos < number_of_queries; ++pos) {
  173.     long long query;
  174.     std::cin >> query;
  175.     queries.push_back(query);
  176.   }
  177.   std::pair<vector<long long>, vector<long long>> answer;
  178.   answer.first = keys;
  179.   answer.second = queries;
  180.   return answer;
  181. }
  182.  
  183. vector<bool> Solve(std::pair<vector<long long>, vector<long long>> input) {
  184.   vector<long long> keys = input.first;
  185.   vector<long long> queries = input.second;
  186.   vector<bool> answer;
  187.   FixedSet set;
  188.   set.Initialize(keys);
  189.   for (auto query : queries) {
  190.     answer.push_back(set.Contains(query));
  191.   }
  192.   return answer;
  193. }
  194.  
  195. void Print(const vector<bool>& answer) {
  196.   for (auto ans : answer) {
  197.     if (ans == false) {
  198.       std::cout << "No"
  199.                 << "\n";
  200.     } else {
  201.       std::cout << "Yes"
  202.                 << "\n";
  203.     }
  204.   }
  205. }
  206.  
  207. int main() {
  208.   std::cin.tie(nullptr);
  209.   std::ios_base::sync_with_stdio(false);
  210.   std::pair<vector<long long>, vector<long long>> Data = ReadInput();
  211.   vector<bool> result = Solve(Data);
  212.   Print(result);
  213.   return 0;
  214. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement