Cod sursa(job #2792145)

Utilizator Teodor94Teodor Plop Teodor94 Data 31 octombrie 2021 23:46:16
Problema Dtcsu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <stdio.h>
#include <ctype.h>
#include <vector>
using namespace std;

#define int64 long long
#define NO_NUMBERS 276997

FILE *fin, *fout;

#define BUF_SIZE 4096
char buf[BUF_SIZE];
int pos = BUF_SIZE;
inline char getChar() {
  if (pos == BUF_SIZE) {
    fread(buf, 1, BUF_SIZE, fin);
    pos = 0;
  }
  return buf[pos++];
}
inline int64 readInt64() {
  int64 result = 0;
  char c;
  do {
    c = getChar();
  } while (!isdigit(c));

  do {
    result = result * 10 + c - '0';
    c = getChar();
  } while (isdigit(c));

  return result;
}

int64 removePow2(int64 x) {
  int step;

  step = 32;
  while (step) {
    if ((x & (((int64)1 << step) - 1)) == 0)
      x >>= step;
    step >>= 1;
  }

  return x;
}

#define HASH_SIZE 100007

vector<int64> myHash[HASH_SIZE];

inline int computeHash(int64 value) {
  return value % HASH_SIZE;
}

inline void insert(int64 value) {
  myHash[computeHash(value)].push_back(value);
}

inline bool find(int64 value) {
  int hash;
  unsigned int i;

  hash = computeHash(value);
  i = 0;
  while (i < myHash[hash].size() && myHash[hash][i] != value)
    ++i;

  return i < myHash[hash].size();
}

int main() {
  fin = fopen("dtcsu.in", "r");
  fout = fopen("dtcsu.out", "w");

  int i, q, counter;
  int64 x;

  for (i = 0; i < NO_NUMBERS; ++i) {
    x = readInt64();

    if (x & 1)
      insert(x);
  }

  counter = 0;
  q = readInt64();
  while (q--) {
    x = readInt64();
    x = removePow2(x);

    counter += find(x);
  }

  fprintf(fout, "%d\n", counter);

  fclose(fin);
  fclose(fout);
  return 0;
}