Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <string>
- #include <iostream>
- using namespace std;
- const int SIZE = 1e6;
- struct Node {
- int data = 0;
- Node *next = nullptr;
- bool is_used = false;
- void insert(int num) {
- if (this->is_used) {
- if (this->data != num) {
- insert_to_next(num);
- }
- } else {
- this->is_used = true;
- this->data = num;
- }
- }
- void insert_to_next(int num) {
- if (!next) {
- next = new Node;
- }
- next->insert(num);
- }
- bool exists(int num) {
- if (this->equals(num)) {
- return true;
- }
- if (this->next) {
- return this->next->exists(num);
- }
- return false;
- }
- void remove(int num) {
- if (this->equals(num)) {
- this->is_used = false;
- } else if (this->next) {
- this->next->remove(num);
- }
- }
- bool equals(int num) {
- return this->is_used && this->data == num;
- }
- };
- struct Set {
- Node *hash_to_node[SIZE + 10]{};
- Set() {
- for (int hash = 0; hash < SIZE + 5; ++hash) {
- hash_to_node[hash] = new Node;
- }
- }
- void insert(int num) {
- int hash = Set::get_hash(num);
- hash_to_node[hash]->insert(num);
- }
- bool exists(int num) {
- int hash = Set::get_hash(num);
- return hash_to_node[hash]->exists(num);
- }
- void remove(int num) {
- int hash = Set::get_hash(num);
- this->hash_to_node[hash]->remove(num);
- }
- static int get_hash(int num) {
- return abs(num) % SIZE;
- }
- };
- int main() {
- Set set;
- string s;
- int num;
- while (cin >> s >> num) {
- if (s == "insert") {
- set.insert(num);
- } else if (s == "exists") {
- cout << (set.exists(num) ? "true" : "false") << endl;
- } else if (s == "delete") {
- set.remove(num);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement