SHARE
TWEET

Untitled

a guest Nov 22nd, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <string>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. const int SIZE = 1e6;
  7.  
  8. struct Node {
  9.     int data = 0;
  10.     Node *next = nullptr;
  11.     bool is_used = false;
  12.  
  13.     void insert(int num) {
  14.         if (this->is_used) {
  15.             if (this->data != num) {
  16.                 insert_to_next(num);
  17.             }
  18.         } else {
  19.             this->is_used = true;
  20.             this->data = num;
  21.         }
  22.     }
  23.  
  24.     void insert_to_next(int num) {
  25.         if (!next) {
  26.             next = new Node;
  27.         }
  28.         next->insert(num);
  29.     }
  30.  
  31.     bool exists(int num) {
  32.         if (this->equals(num)) {
  33.             return true;
  34.         }
  35.         if (this->next) {
  36.             return this->next->exists(num);
  37.         }
  38.         return false;
  39.     }
  40.  
  41.     void remove(int num) {
  42.         if (this->equals(num)) {
  43.             this->is_used = false;
  44.         } else if (this->next) {
  45.             this->next->remove(num);
  46.         }
  47.     }
  48.  
  49.     bool equals(int num) {
  50.         return this->is_used && this->data == num;
  51.     }
  52. };
  53.  
  54. struct Set {
  55.     Node *hash_to_node[SIZE + 10]{};
  56.  
  57.     Set() {
  58.         for (int hash = 0; hash < SIZE + 5; ++hash) {
  59.             hash_to_node[hash] = new Node;
  60.         }
  61.     }
  62.  
  63.     void insert(int num) {
  64.         int hash = Set::get_hash(num);
  65.         hash_to_node[hash]->insert(num);
  66.     }
  67.  
  68.     bool exists(int num) {
  69.         int hash = Set::get_hash(num);
  70.         return hash_to_node[hash]->exists(num);
  71.     }
  72.  
  73.     void remove(int num) {
  74.         int hash = Set::get_hash(num);
  75.         this->hash_to_node[hash]->remove(num);
  76.     }
  77.  
  78.     static int get_hash(int num) {
  79.         return abs(num) % SIZE;
  80.     }
  81. };
  82.  
  83.  
  84. int main() {
  85.     Set set;
  86.     string s;
  87.     int num;
  88.  
  89.     while (cin >> s >> num) {
  90.         if (s == "insert") {
  91.             set.insert(num);
  92.         } else if (s == "exists") {
  93.             cout << (set.exists(num) ? "true" : "false") << endl;
  94.         } else if (s == "delete") {
  95.             set.remove(num);
  96.         }
  97.     }
  98.  
  99.     return 0;
  100. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top