Pagini recente » Cod sursa (job #1579548) | Cod sursa (job #2879836) | Cod sursa (job #2326883) | Cod sursa (job #2738596) | Cod sursa (job #916829)
Cod sursa(job #916829)
#include <fstream>
using namespace std;
// A node in a doubly-linked list
template<class T>
class Node {
private:
T val; // The information in the node
Node *next, *prev; // Links to the next/previous nodes
public:
// We only need standard getters and setters
T getVal() {
return val;
}
void setVal(T x) {
val = x;
}
Node* getPrev() {
return prev;
}
void setPrev(Node *x) {
prev = x;
}
Node* getNext() {
return next;
}
void setNext(Node *x) {
next = x;
}
};
// A doubly-linked list; it contains Node elements
template<class T>
class List {
private:
int size; // How many elements the list contains
Node<T> *start, *end; // References to the start and end
// of the list
public:
int getSize() {
return size;
}
Node<T>* getStart() {
return start;
}
// Adds an element at the end of the list
void add(T val) {
if(size == 0) {
start = end = new Node<T>;
start->setVal(val);
} else {
Node<T> *n = new Node<T>;
n->setVal(val);
n->setPrev(end);
end->setNext(n);
end = n;
}
size ++;
}
// Deletes all occurrences of val from the list
// this is O(n), should only be used on small
// lists
void del(T val) {
if(size == 0) {
return;
} else if(size == 1) {
if(start->getVal() == val) {
delete start;
start = end = NULL;
size --;
}
} else {
Node<T> *p = start, *q;
while(p != NULL) {
if(p->getVal() == val) {
if(p->getPrev() != NULL) {
p->getPrev()->setNext(p->getNext());
}
if(p->getNext() != NULL) {
p->getNext()->setPrev(p->getPrev());
}
q = p;
p = p->getNext();
delete q;
size --;
continue;
}
p = p->getNext();
}
}
}
// Searches for val in the list; returns 1 if val is in the
// list, and 0 otherwise
int search(T val) {
if(size == 0) {
return 0;
} else if(size == 1) {
return start->getVal() == val;
} else {
Node<T> *p = start;
while(p != NULL) {
if(p->getVal() == val) {
return 1;
}
p = p->getNext();
}
return 0;
}
}
};
// The hash. Internally, it contains two simple hashes,
// and a value is stored in the most convenient of them
template<class T>
class Hash {
private:
List<T> *H1;
List<T> *H2;
int n1;
int n2;
int (*hash_func)(int, T);
int max_size;
// When a list exceedes a certain length, rehash it
void rehash(List<T> *l, List<T> *h, int n) {
Node<T> *p = l->getStart();
while(p != NULL) {
h[hash_func(n, p->getVal())].add(p->getVal());
p = p->getNext();
delete p->getPrev();
}
}
public:
// A hash is created from two hash sizes and a hash function.
// The hash function takes (n, val) as arguments,
// where val is the hashed value, and returns an integer
// between 0 and n-1, inclusively
Hash(int n, int m, int (h)(int, T)) {
max_size = 10;
hash_func = h;
H1 = new List<T>[n];
H2 = new List<T>[m];
n1 = n;
n2 = m;
}
// An item is added to the hash like this:
// hash += value
// This method also rehashes if needed
void operator+=(T val) {
List<T> *a = &H1[hash_func(n1, val)], *b = &H2[hash_func(n2, val)];
if(a->getSize() > max_size) {
rehash(a, H2, n2);
}
if(b->getSize() > max_size) {
rehash(b, H1, n1);
}
if(a->getSize() < b->getSize()) {
a->add(val);
} else {
b->add(val);
}
}
// An item is removed from the hash like this:
// hash -= value
void operator-=(T val) {
H1[hash_func(n1, val)].del(val);
H2[hash_func(n2, val)].del(val);
}
// A hash lookup looks like this:
// hash[value] // 1 if value is found, 0 otherwise
int operator[](T val) {
return H1[hash_func(n1, val)].search(val)
|| H2[hash_func(n2, val)].search(val);
}
};
// standard, simple hash function
int hash_int(int n, int val) {
return val % n;
}
int main() {
ifstream in("hashuri.in");
ofstream out("hashuri.out");
Hash<int> h(66047, 96557, hash_int);
int n, op, v, i;
in>>n;
for(i=0; i<n; i++) {
in>>op>>v;
if(op == 1) {
h += v;
} else if(op == 2) {
h -= v;
} else {
out<<h[v]<<'\n';
}
}
return 0;
}