Pagini recente » Cod sursa (job #541674) | Cod sursa (job #2903884) | Cod sursa (job #1683896) | Cod sursa (job #2863886) | Cod sursa (job #1034153)
#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) );
}
public:
BloomFilter(){
memset(B, 0, sizeof(B));
}
void update(unsigned long long x){
for (unsigned long long i = 0 ; i < nrHash ; i++)
setBit(x + (1 << i));
}
bool query(unsigned long long x){
for (unsigned long long i = 0 ; i < nrHash ; i++)
if (!getBit(x + (1 << 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, "%I64d", &x);
ans += B.query(x);
}
fprintf(out, "%d\n", ans);
return 0;
}