Cod sursa(job #1040816)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 24 noiembrie 2013 22:45:20
Problema Dtcsu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <bitset>

using namespace std;

const int CNT = 276997;
const int B_MAX = 1000;
const int BITSET_MAX = 6000000;

int N, poz, cnt;
int REST[K_MAX] = {5901353, 5919271, 5962711, 5998691}, MUL[K_MAX] = {3, 11, 5, 7};
unsigned long long A;
char buff[B_MAX];

bitset<BITSET_MAX> V[K_MAX];

inline unsigned long long getLongLong() {
    while(!isdigit(buff[poz]))
        if(++poz == B_MAX) fread(buff, 1, B_MAX, stdin), poz = 0;
    unsigned long long ans = 0;
    while(isdigit(buff[poz])) {
        ans = ans * 10 + buff[poz++] - '0';
        if(poz == B_MAX) fread(buff, 1, B_MAX, stdin), poz = 0;
    } return ans;
}

inline int getHashCode(const unsigned long long &X, const int &A) {
    return (X * MUL[A]) % REST[A];
}

inline void addToBloomFilter(const unsigned long long &X) {
    for(int i = 0; i < 4; i++)
        V[getHashCode(X, i)] = true;
}

inline bool inBloomFilter(const unsigned long long &X) {
    for(int i = 0; i < 4; i++)
        if(!V[getHashCode(X, i)]) return false;
    return true;
}

int main() {
    freopen("dtcsu.in", "r", stdin); freopen("dtcsu.out", "w", stdout);
    fread(buff, 1, B_MAX, stdin);
    for(int i = 1; i <= CNT; i++) {
        A = getLongLong();
        addToBloomFilter(A);
    } N = getLongLong();
    for(int i = 1; i <= N; i++) {
        A = getLongLong();
        if(inBloomFilter(A)) cnt++;
    } printf("%d\n", cnt);
    fclose(stdin); fclose(stdout);
    return 0;
}