Cod sursa(job #1040791)

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

using namespace std;

const int CNT = 276997;
const int B_MAX = 1000;
const int K_MAX = 3;
const int BITSET_MAX = 2000000;

int N, poz, cnt;
int REST[K_MAX] = {1971889, 1988243, 1999817}, MUL[K_MAX] = {31, 83,59};
long long A;
char buff[B_MAX];

bitset<BITSET_MAX> V[K_MAX];

inline long long getLongLong() {
    while(!isdigit(buff[poz]))
        if(++poz == B_MAX) fread(buff, 1, B_MAX, stdin), poz = 0;
    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 long long &X, const int &A) {
    return (X * MUL[A]) % REST[A];
}

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

inline bool inBloomFilter(const long long &X) {
    for(int i = 0; i < 3; i++)
        if(!V[i][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;
}