Cod sursa(job #3319019)

Utilizator Andrei_PanaAndrei Pana Andrei_Pana Data 30 octombrie 2025 12:01:30
Problema Dtcsu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

ifstream cin("dtcsu.in");
ofstream cout("dtcsu.out");

struct hashtable{
  static const int P2EXP=10;
  static const int MAXHASH=1024;

  int RANDOM;
  vector<int> vals[MAXHASH+1];

  int hash(int val){
    return val&((1<<P2EXP)-1);
  }

  hashtable(){
    srand(time(NULL));
    RANDOM=this->hash(rand());
  }

  void insert(int x){
    if(!this->contains(x)){
      int code=this->hash(RANDOM*x);
      vals[code].push_back(x);
    }
  }

  void erase(int x){
    if(this->contains(x)){
      int code=this->hash(RANDOM*x);
      auto pos=find(vals[code].begin(),vals[code].end(),x);
      *pos=vals[code].back();
      vals[code].pop_back();
    }
  }

  bool contains(int x){
    int code=this->hash(RANDOM*x);
    return (find(vals[code].begin(),vals[code].end(),x)!=vals[code].end());
  }
}hsh;

int main(){
  int n=276997,i,q,nrbun=0;
  long long x;

  for(i=0;i<n;i++){
    cin>>x;
    hsh.insert(x);
  }

  cin>>q;
  while(q--){
    cin>>x;
    nrbun+=hsh.contains(x);
  }
  cout<<nrbun;

  return 0;
}