Cod sursa(job #1034160)

Utilizator mihai995mihai995 mihai995 Data 17 noiembrie 2013 18:15:29
Problema Dtcsu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <cstring>
using namespace std;

template<const int Size, const int nrHash>
class BloomFilter{
    unsigned char B[1 + (Size >> 3)];

    inline void setBit(unsigned long long x){
        x &= Size;
        B[x >> 3] |= 1 << (x & 7);
    }

    inline bool getBit(unsigned long long x){
        x %= Size;
        return B[x >> 3] & ( 1 << (x & 7) );
    }

    inline unsigned long long hash(unsigned long long x, unsigned long long i){
        return x * x * x;
    }

public:
    BloomFilter(){
        memset(B, 0, sizeof(B));
    }
    void update(unsigned long long x){
        for (unsigned long long i = 0 ; i < nrHash ; i++)
            setBit( hash(x, i) );
    }

    bool query(unsigned long long x){
        for (unsigned long long i = 0 ; i < nrHash ; i++)
            if (!getBit( hash(x, i) ))
                return false;
        return true;
    }
};

BloomFilter<4682861, 60> B;
const int buffSize = 1 << 17;
char buff[buffSize];

int main(){
    int times = 276997, ans = 0;
    long long x;

    FILE* in = fopen("dtcsu.in", "r");
    FILE* out = fopen("dtcsu.out", "w");
    setvbuf(in, buff, _IOFBF, buffSize);

    while (times--){
        fscanf(in, "%lld", &x);
        B.update(x);
    }

    fscanf(in, "%d", &times);
    while (times--){
        fscanf(in, "%lld", &x);
        ans += B.query(x);
    }

    fprintf(out, "%d\n", ans);

    return 0;
}