Cod sursa(job #1875902)

Utilizator tudoras8tudoras8 tudoras8 Data 11 februarie 2017 19:14:45
Problema Hashuri Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <forward_list>

using namespace std;

class HashTable {
public:
    HashTable(int bucket_count)
        : bucket_count(bucket_count), buckets(bucket_count) {
        
    }
    void insert(int val) {
        if (!contains(val)) {
            int bucket = hashvalue(val);
            buckets[bucket].push_front(val);
        }
    }
    void remove(int val) {
        int bucket = hashvalue(val);
        buckets[bucket].remove(val);
    }
    int lookup(int val) {
        return contains(val) ? 1 : 0;
    }
private:
    int bucket_count;
    
    vector<forward_list<int>> buckets;
    
    int hashvalue(int val) {
        return val % bucket_count;
    }
    
    bool contains(int val) {
        int bucket = hashvalue(val);
        for (int x : buckets[bucket]) {
            if (x == val) {
                return true;
            }
        }
        return false;
    }
};

int main(int argc, const char * argv[]) {
    ifstream cin("hashuri.in");
    ofstream cout("hashuri.out");
    
    int n;
    cin >> n;
    
    HashTable t(7368787); // 7,368,787 is the 500,000th prime number
    while (n--) {
        int op, x;
        cin >> op >> x;
        
        switch (op) {
            case 1:
                // insert
                t.insert(x);
                break;
            case 2:
                // remove
                t.remove(x);
                break;
            case 3:
                // lookup
                cout << t.lookup(x) << '\n';
                break;
        }
    }
    
    return 0;
}