Cod sursa(job #3142504)

Utilizator daristyleBejan Darius-Ramon daristyle Data 22 iulie 2023 00:05:22
Problema Dtcsu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>

using namespace std;
ifstream fin("dtcsu.in");
ofstream fout("dtcsu.out");

const int DTCSU_NUMBERS = 276997;
const int NIL = -1;

template<typename T>
class HashTable{
private:
		static const int MOD = 202393;
		int head[MOD];
		int key[DTCSU_NUMBERS], nxt[DTCSU_NUMBERS];
		int n;

		static inline int hash(T x){
			return x % MOD;
		}

public:
		HashTable(){
			for(int i = 0; i < DTCSU_NUMBERS; ++i)
				nxt[i] = NIL;
			for(int i = 0; i < MOD; ++i)
				head[i] = NIL;
			n = 0;
		}

		void init(){
			for(int i = 0; i < DTCSU_NUMBERS; ++i)
				nxt[i] = NIL;
			for(int i = 0; i < MOD; ++i)
				head[i] = NIL;
			n = 0;
		}

		void add(T x){
			int list = hash(x);
			key[n] = x;
			nxt[n] = head[list];
			head[list] = n;
			++n;
		}

		void remove(T x){
			int list = hash(x);
			int l = head[list], prev = NIL;
			while(l != NIL && key[l] != x){
				prev = l;
				l = nxt[l];
			}

			if(l != NIL && key[l] == x){
				if(prev == NIL)
					head[list] = nxt[l];
				else
					nxt[prev] = nxt[l];
			}
		}

		bool find(T x){
			int list = hash(x);
			int l = head[list];
			while(l != NIL && key[l] != x)
				l = nxt[l];

			return l != NIL;
		}

		void clear(){
			init();
		}
};

HashTable<long long> f{};

int main(){
	long long x;
	int queries;
	for(int i = 0; i < DTCSU_NUMBERS; ++i){
		fin >> x;
		f.add(x);
	}

	int cnt = 0;
	fin >> queries;
	for(int query = 0; query < queries; ++query){
		fin >> x;
		cnt += f.find(x);
	}

	fout << cnt << '\n';

	fin.close();
	fout.close();
	return 0;
}