Cod sursa(job #2595134)

Utilizator luc1anDascalescu Lucian luc1an Data 7 aprilie 2020 11:01:24
Problema Dtcsu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>


typedef  unsigned long long int uint64_t;
typedef  unsigned int uint32_t;
#define nrnr  276997
#define m  2769976
#define k 6



uint64_t hash(const uint64_t& n) {
	uint64_t x = n;
	x = (x ^ (x >> 30)) * uint64_t(0xbf58476d1ce4e5b9);
	x = (x ^ (x >> 27)) * uint64_t(0x94d049bb133111eb);
	x = x ^ (x >> 31);
	return x;
}

uint64_t v[nrnr];
char bloom [m / 8];
int output;

void setbit(const uint32_t& x) {
	bloom[x / 8] = bloom[x / 8] | (1 << (x % 8));
}

int checkbit(const uint32_t& x) {
	if (bloom[x / 8] & (1 << (x % 8))) return 1;
	return 0;
}

void updatebloom(const int& i) {
	uint64_t h = hash(v[i]);
	uint32_t h1 = h >> 32;
	uint32_t h2 = h << 32;

	uint32_t ha = h1;
	for (int i = 0; i < k; i++) {
		ha = ha + (k*h2);
		
		setbit(ha%m);
	}

}

int querybloom(const uint64_t& x) {
	uint64_t h = hash(x);
	uint32_t h1 = h >> 32;
	uint32_t h2 = h << 32;

	uint32_t ha = h1;
	for (int i = 0; i < k; i++) {
		ha = ha + (k*h2);

		if (checkbit(ha%m) == 0) {
			return 0;
		}
	}

	return 1;
}

int main() {
	FILE* fi = fopen("dtcsu.in", "r");
	char buff[32];

	for (int i = 0; i < nrnr; i++) {
		fgets(buff, 32, fi);
		v[i] = strtoull(buff, NULL, 10);
		updatebloom(i);
	}

	int Q;
	fgets(buff, 32, fi);;
	Q = atoi(buff);

	uint64_t N;
	for (int i = 0; i < Q; i++) {
		fgets(buff, 32, fi);
		N = strtoull(buff, NULL, 10);

		if (querybloom(N)) {
			for (int j = 0; j < nrnr; j++) {
				if (v[j] == N) {
					output++;
					break;
				}
			}
		}
	}

	FILE* fo = fopen("dtcsu.out", "w");
	fprintf(fo, "%d", output);

	fclose(fi);
	fclose(fo);
	return 0;
}