Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdio.h>
- #include <vector>
- #include <string>
- #include <math.h>
- #include <algorithm>
- #include <map>
- #include <set>
- #include <stack>
- #include <functional>
- #include <list>
- #include <ctime>
- std::vector<int> ReadSetElements(std::istream& in_stream = std::cin) {
- int quantity;
- in_stream >> quantity;
- std::vector<int> numbers(quantity);
- for (int& number : numbers) {
- in_stream >> number;
- }
- return numbers;
- }
- std::vector<int> ReadQueries(std::istream& in_stream = std::cin) {
- int quantity;
- in_stream >> quantity;
- std::vector<int> queries(quantity);
- for (int& query : queries) {
- in_stream >> query;
- }
- return queries;
- }
- class HashFunction {
- int multiplier;
- int shift;
- int prime;
- int modulo;
- public:
- HashFunction() = default;
- HashFunction(int new_multiplier, int new_shift, int new_prime, int new_modulo)
- : multiplier(new_multiplier), shift(new_shift), prime(new_prime),
- modulo(new_modulo) {}
- int operator()(int number) const {
- int hash_function_value = (static_cast<int64_t>(multiplier) * number + shift) % prime;
- if (hash_function_value < 0) {
- hash_function_value += prime;
- }
- return hash_function_value % modulo;
- }
- };
- int GenerateRandomNumber(int lower_bound, int upper_bound) {
- static std::default_random_engine generator;
- static std::uniform_int_distribution<int> distribution(lower_bound,
- upper_bound);
- return distribution(generator);
- }
- HashFunction GenerateRandomHashFunction(int prime, int modulo) {
- const int multiplier_coeficient = GenerateRandomNumber(1, prime);
- const int shift_coeficient = GenerateRandomNumber(0, prime);
- return {multiplier_coeficient, shift_coeficient, prime, modulo};
- }
- constexpr int kDefaultPrimeModulo = 2000000011;
- class SecondLevelHashTable {
- public:
- void Initialize(const std::vector<int>& numbers) {
- if (numbers.empty()) {
- return;
- }
- hash_function = GenerateHashFunctionWithoutCollisions(numbers);
- data.assign(numbers.size() * numbers.size(), kEmptyCell);
- for (const int number : numbers) {
- data[hash_function(number)] = number;
- }
- }
- bool Contains(const int number) const {
- return !data.empty() && data[hash_function(number)] == number;
- }
- private:
- std::vector<int> data;
- HashFunction hash_function;
- static constexpr int kEmptyCell = 2000000000;
- static HashFunction GenerateHashFunctionWithoutCollisions(
- const std::vector<int>& numbers) {
- HashFunction possible_hash_function;
- bool has_collisions = true;
- do {
- std::vector<int> table(numbers.size() * numbers.size(), kEmptyCell);
- possible_hash_function = GenerateRandomHashFunction(kDefaultPrimeModulo,
- numbers.size() *
- numbers.size());
- has_collisions = false;
- for (const int number : numbers) {
- const int hash = possible_hash_function(number);
- if (table[hash] == kEmptyCell) {
- table[hash] = number;
- } else if (table[hash] != number) {
- has_collisions = true;
- }
- }
- } while (has_collisions);
- return possible_hash_function;
- }
- };
- constexpr int SecondLevelHashTable::kEmptyCell;
- std::vector<int> CalculateChainsSizes(const std::vector<int>& numbers,
- const HashFunction& outer_hash_function) {
- std::vector<int> chains_sizes(numbers.size(), 0);
- for (const int number : numbers) {
- const int hash = outer_hash_function(number);
- ++chains_sizes[hash];
- }
- return chains_sizes;
- }
- int64_t CalculateSumOfSquares(const std::vector<int>& numbers) {
- int64_t sum_of_squares = 0;
- for (const int item : numbers) {
- sum_of_squares += static_cast<int64_t>(item) * item;
- }
- return sum_of_squares;
- }
- class FixedSet {
- public:
- void Initialize(const std::vector<int>& numbers) {
- outer_hash_function = GenerateFittingHashFunction(numbers);
- FillHashTables(numbers);
- }
- bool Contains(int number) const {
- const int hash = outer_hash_function(number);
- return double_hash_table[hash].Contains(number);
- }
- private:
- using Bucket = std::vector<int>;
- std::vector<SecondLevelHashTable> double_hash_table;
- HashFunction outer_hash_function;
- static constexpr int kMaxSumOfSquaresRatio = 4;
- static bool HashFunctionFits(
- const HashFunction& possible_outer_hash_function,
- const std::vector<int>& numbers) {
- std::vector<int> chains_sizes = CalculateChainsSizes(numbers,
- possible_outer_hash_function);
- return CalculateSumOfSquares(chains_sizes) <= kMaxSumOfSquaresRatio * numbers.size();
- }
- static HashFunction GenerateFittingHashFunction(
- const std::vector<int>& numbers) {
- HashFunction possible_outer_hash_function;
- do {
- possible_outer_hash_function = GenerateRandomHashFunction(kDefaultPrimeModulo,
- numbers.size());
- } while (!HashFunctionFits(possible_outer_hash_function, numbers));
- return possible_outer_hash_function;
- }
- void FillDoubleHashTable(const std::vector<Bucket>& classes) {
- double_hash_table.reserve(classes.size());
- for (const Bucket& one_class : classes) {
- SecondLevelHashTable inner_hash_table;
- inner_hash_table.Initialize(one_class);
- double_hash_table.push_back(inner_hash_table);
- }
- }
- void FillHashTables(const std::vector<int>& numbers) {
- std::vector<Bucket> classes(numbers.size());
- for (const int item : numbers) {
- classes[outer_hash_function(item)].push_back(item);
- }
- FillDoubleHashTable(classes);
- }
- };
- FixedSet BuildFixedSetFromInput(std::istream& in_stream = std::cin) {
- const std::vector<int> numbers = ReadSetElements(in_stream);
- FixedSet fixed_set;
- fixed_set.Initialize(numbers);
- return fixed_set;
- }
- std::vector<bool> AnswerQueries(const FixedSet& fixed_set,
- const std::vector<int>& queries) {
- std::vector<bool> answers;
- answers.reserve(queries.size());
- for (const int query : queries) {
- answers.push_back(fixed_set.Contains(query));
- }
- return answers;
- }
- void WriteAnswers(const std::vector<bool>& answers,
- std::ostream& out_stream = std::cout) {
- for (const bool answer : answers) {
- out_stream << (answer ? "Yes" : "No") << '\n';
- }
- }
- int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
- const FixedSet fixed_set = BuildFixedSetFromInput();
- const std::vector<int> queries = ReadQueries();
- const std::vector<bool> answers = AnswerQueries(fixed_set, queries);
- WriteAnswers(answers);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement