Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <random>
- #include <utility>
- #include <vector>
- using std::vector;
- class HashFunction;
- class FixedSet;
- std::pair<vector<long long>, vector<long long>> ReadInput();
- vector<bool> Solve(std::pair<vector<long long>, vector<long long>> input);
- void Print(const vector<bool>& answer);
- class HashFunction {
- public:
- void InitializeRandomly(long long mod, std::mt19937* generator);
- long long Count(long long input) const;
- private:
- long long multiplier, adder;
- long long module = 1;
- long long prime = 2000000011;
- };
- class FixedSet {
- public:
- FixedSet() {}
- void Initialize(const vector<long long>& data);
- bool Contains(long long number) const;
- private:
- vector<vector<long long>> hash_table;
- HashFunction upper_hash;
- vector<HashFunction> list_of_down_hashes;
- long long quantity_of_buckets = 0;
- long long not_in_set = 2000000000;
- const int upper_level = 1;
- const int down_level = -1;
- bool IsOkHashFunction(int level, HashFunction hash,
- const vector<long long>& data);
- HashFunction ChoosePerfectHash(const vector<long long>& data,
- std::mt19937* generator);
- vector<long long> BucketsOfPerfectHash(HashFunction hash,
- long long number_of_buckets,
- const vector<long long>& data);
- HashFunction ChooseUpperHash(const vector<long long> keys,
- std::mt19937* generator);
- vector<vector<long long>> BucketsOfUpperHash(HashFunction hash,
- const vector<long long>& data);
- };
- void HashFunction::InitializeRandomly(long long mod, std::mt19937* generator) {
- std::uniform_int_distribution<> dis(0, prime);
- multiplier = dis(*generator);
- adder = dis(*generator);
- if (mod > 0) {
- module = mod;
- }
- }
- long long HashFunction::Count(long long input) const {
- return ((multiplier * ((input + prime) % prime) + adder) % prime) % module;
- }
- void FixedSet::Initialize(const vector<long long>& data) {
- std::random_device random;
- std::mt19937 gen(random());
- vector<vector<long long>> list_of_buckets;
- quantity_of_buckets = data.size();
- upper_hash = ChooseUpperHash(data, &gen);
- list_of_buckets = BucketsOfUpperHash(upper_hash, data);
- for (int bucket_number = 0; bucket_number < quantity_of_buckets;
- ++bucket_number) {
- HashFunction current_hash =
- ChoosePerfectHash(list_of_buckets[bucket_number], &gen);
- list_of_down_hashes.push_back(current_hash);
- long long current_bucket_size_squared =
- list_of_buckets[bucket_number].size() *
- list_of_buckets[bucket_number].size();
- hash_table.push_back(BucketsOfPerfectHash(current_hash,
- current_bucket_size_squared,
- list_of_buckets[bucket_number]));
- }
- }
- bool FixedSet::Contains(long long number) const {
- if (quantity_of_buckets == 0) {
- return false;
- }
- HashFunction down_hash = list_of_down_hashes[upper_hash.Count(number)];
- return hash_table[upper_hash.Count(number)][down_hash.Count(number)] ==
- number;
- }
- bool FixedSet::IsOkHashFunction(int level, HashFunction hash,
- const vector<long long>& data) {
- if (level == upper_level) {
- vector<int> sizes_of_buckets(data.size());
- size_t sum_of_squares_of_sizes = 0;
- for (auto key : data) {
- sizes_of_buckets[hash.Count(key)] += 1;
- }
- for (auto size : sizes_of_buckets) {
- sum_of_squares_of_sizes += size * size;
- }
- return sum_of_squares_of_sizes <= 4 * data.size();
- } else {
- for (size_t left = 0; left < data.size(); ++left) {
- for (size_t right = left + 1; right < data.size(); ++right) {
- if (hash.Count(data[left]) == hash.Count(data[right])) {
- return false;
- }
- }
- }
- }
- return true;
- }
- HashFunction FixedSet::ChoosePerfectHash(const vector<long long>& data,
- std::mt19937* generator) {
- HashFunction perfect_hash;
- perfect_hash.InitializeRandomly(data.size() * data.size(), generator);
- while (not IsOkHashFunction(down_level, perfect_hash, data)) {
- perfect_hash.InitializeRandomly(data.size() * data.size(), generator);
- }
- return perfect_hash;
- }
- vector<long long> FixedSet::BucketsOfPerfectHash(
- HashFunction hash, long long number_of_buckets,
- const vector<long long>& data) {
- vector<long long> answer(number_of_buckets + 1, not_in_set);
- for (auto key : data) {
- answer[hash.Count(key)] = key;
- }
- return answer;
- }
- HashFunction FixedSet::ChooseUpperHash(const vector<long long> keys,
- std::mt19937* generator) {
- HashFunction desired_hash;
- desired_hash.InitializeRandomly(quantity_of_buckets, generator);
- while (not IsOkHashFunction(upper_level, desired_hash, keys)) {
- desired_hash.InitializeRandomly(quantity_of_buckets, generator);
- }
- return desired_hash;
- }
- vector<vector<long long>> FixedSet::BucketsOfUpperHash(
- HashFunction hash, const vector<long long>& data) {
- vector<vector<long long>> answer(data.size(), vector<long long>());
- for (auto key : data) {
- answer[hash.Count(key)].push_back(key);
- }
- return answer;
- }
- std::pair<vector<long long>, vector<long long>> ReadInput() {
- vector<long long> keys;
- vector<long long> queries;
- int size_of_set;
- std::cin >> size_of_set;
- for (int pos = 0; pos < size_of_set; ++pos) {
- long long key;
- std::cin >> key;
- keys.push_back(key);
- }
- int number_of_queries;
- std::cin >> number_of_queries;
- for (int pos = 0; pos < number_of_queries; ++pos) {
- long long query;
- std::cin >> query;
- queries.push_back(query);
- }
- std::pair<vector<long long>, vector<long long>> answer;
- answer.first = keys;
- answer.second = queries;
- return answer;
- }
- vector<bool> Solve(std::pair<vector<long long>, vector<long long>> input) {
- vector<long long> keys = input.first;
- vector<long long> queries = input.second;
- vector<bool> answer;
- FixedSet set;
- set.Initialize(keys);
- for (auto query : queries) {
- answer.push_back(set.Contains(query));
- }
- return answer;
- }
- void Print(const vector<bool>& answer) {
- for (auto ans : answer) {
- if (ans == false) {
- std::cout << "No"
- << "\n";
- } else {
- std::cout << "Yes"
- << "\n";
- }
- }
- }
- int main() {
- std::cin.tie(nullptr);
- std::ios_base::sync_with_stdio(false);
- std::pair<vector<long long>, vector<long long>> Data = ReadInput();
- vector<bool> result = Solve(Data);
- Print(result);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement