Cod sursa(job #2595385)

Utilizator luc1anDascalescu Lucian luc1an Data 7 aprilie 2020 17:05:43
Problema Dtcsu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 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 xorshift(const uint64_t& n, int i) {
	return n ^ (n >> i);
}
uint64_t hash(const uint64_t& n) {
	uint64_t p = 0x5555555555555555;
	uint64_t c = 17316035218449499591ull;
	return c * xorshift(p*xorshift(n, 32), 32);
}

//uint64_t v[nrnr];
uint64_t v[nrnr*2];
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);
		uint64_t nr = strtoull(buff, NULL, 10);
		uint64_t h = hash(nr);
		int index = h % (nrnr * 2);
		
		while (v[index] != 0) index++;
		v[index] = nr;
		
		
		uint32_t h1 = h >> 32;
		uint32_t h2 = h << 32;

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

			setbit(ha%m);
		}


	}

	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;
				}
			}*/

			uint64_t h = hash(N);
			int index = h % (nrnr * 2);

			while (v[index] != 0) {
				if (v[index] == N) {
					output++;
					break;
				}
				index++;
			}

		}
	}

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

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