Cod sursa(job #907449)

Utilizator blechereyalBlecher Eyal blechereyal Data 7 martie 2013 22:41:57
Problema Hashuri Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 3.65 kb
#include <math.h>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <time.h>
#define prim 1000000009

using namespace std;

class cuckoo_set
{
    int mod;
    int *hash;
    int hash_size;
    int a,b,c,d;
    public:

    cuckoo_set(int size)
        {
        hash = new int[size];
        hash_size = size;
        fill(hash,hash+size,0);
        }

    int insert(int value)
    {
    int cycles=0,aux=value,which=1;
    bool found=false;

    if (find(value)) return 1;
    while (!found)
                {
                int poz1 = function1(value);
                int poz2 = function2(value);
                cycles++;
                if (hash[poz1] == 0)
                    {
                    hash[poz1] = value;
                    found = true;
                    }
                else if(hash[poz2] == 0)
                    {
                    hash[poz2] = value;
                    found = true;
                    }
                    else
                        {
                        if (which==1)
                            {
                            aux = value;
                            value = hash[poz1];
                            hash[poz1] = aux;
                            }
                        else
                            {
                            aux = value;
                            value = hash[poz2];
                            hash[poz2] = aux;
                            }
                        which*=-1;
                        }
        if ((cycles > log2(this->hash_size))&&(!found)){return 0;}//numarul de incercari nu depaseste log size
    }
    return 1;
    }

    void erase(int value)
    {

        int poz1 = function1(value);
        int poz2 = function2(value);
        if (hash[poz1] == value)
            {
            hash[poz1] = 0;
            }
        else if (hash[poz2] == value)
            {
            hash[poz2] = 0;
            }
    }

    int find(int value)
    {
    int poz1 = function1(value);
    int poz2 = function2(value);
    if (hash[poz1] == value || hash[poz2] == value)
    {
        return 1;
    }
    else
    {
        return 0;
    }
    }

    int function1(int value)
    {
        return (((long long)a+(long long)value * (long long)b ) % (long long)prim )% (long long)hash_size;
    }
    int function2(int value)
    {
        return (((long long)c+(long long)value * (long long)d ) % (long long)prim ) %(long long)hash_size;
    }
    void make_hash_function()
    {
         a = rand() % hash_size;
         b = rand() % hash_size;
         c = rand() % hash_size;
         d = rand() % hash_size;

    }
    int rehash(string a, string b)
    {
    bool ok = false;
    ifstream in(a.c_str());
    ofstream out(b.c_str());

    while (ok == false)
    {

        in.clear();

        int N;
        bool ok2=true;
        make_hash_function();
        in >> N;
        for (int i =0;i<N && ok2==true;i++)
        {
            ok2=true;
            int x , op;
            in >> op >> x;
            if (op == 1)
            {
                if ( !insert(x) )
                {
                    ok = false;
                    ok2=false;
                    break;
                }
            }
            if (op == 2)
            {
                erase(x);
            }
            if (op == 3)
            {
                out << find(x) << "\n";
            }
        }
        ok = true;
    }
    return 0;
    }
};

int main()
{   cuckoo_set t(1000001);
    t.rehash("hashuri.in","hashuri.out");
   return 0;
}