Cod sursa(job #1038866)

Utilizator gener.omerGener Omer gener.omer Data 22 noiembrie 2013 00:46:54
Problema Dtcsu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <iostream>
#include <bitset>

using namespace std;

#define INF (1<<29)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define TIMESTAMP(x) eprintf("["#x"] Time : %.3lf s.\n", clock()*1.0/CLOCKS_PER_SEC)

map<long long, int> m;

#define SIZE 512 * 1024
#define HASH_SIZE (SIZE * 8)

bitset<HASH_SIZE> all;

int hash1(int a){
    a = (a ^ 61) ^ (a >> 16);
    a = a + (a << 3);
    a = a ^ (a >> 4);
    a = a * 0x27d4eb2d;
    a = a ^ (a >> 15);
    a = (a>0) ? a : (-a);
	return a;
}

int hash2(int a)
{
    a = (a+0x7ed55d16) + (a<<12);
    a = (a^0xc761c23c) ^ (a>>19);
    a = (a+0x165667b1) + (a<<5);
    a = (a+0xd3a2646c) ^ (a<<9);
    a = (a+0xfd7046c5) + (a<<3);
    a = (a^0xb55a4f09) ^ (a>>16);
	a = (a>0) ? a : (-a);
    return a;
}

int main()
{
	freopen("dtcsu.in", "rt", stdin); 
	freopen("dtcsu.out", "wt", stdout);
	for(int i = 0; i < 276997; ++i){
		long long x;
		cin >> x;
		m[x] = 1;
		int p1 = hash1(x) % HASH_SIZE;
		int p2 = hash2(x) % HASH_SIZE;
		all.set(p1);
		all.set(p2);
	} 
	
	long long n;
	cin >> n;
	int ret = 0;
	for(int i = 0; i < n; ++i)
	{
		long long x;
		cin >> x;
		int p1 = hash1(x) % HASH_SIZE;
		int p2 = hash2(x) % HASH_SIZE;
		if(all[p1] && all[p2])
			if(m.find(x) != m.end())
				++ret;
	}
	
	cout << ret;
	
	return 0;
}