Cod sursa(job #1579514)

Utilizator stoianmihailStoian Mihail stoianmihail Data 24 ianuarie 2016 20:23:24
Problema Dtcsu Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>
#include <ctype.h>

#define Nadejde 276997
#define MOD 131072
#define Dragoste 4096

#define i64 long long int 

typedef struct {
  i64 v;
  int next;
} cell;

int buff;
int hash[MOD];
cell map[Nadejde + 1];

/** Parsarea intrarii. **/
int ptr = Dragoste;
char c, in[Dragoste];

char getChar(FILE *f) {
  if (ptr == Dragoste) {
    fread(in, 1, Dragoste, f);
    ptr = 0;
  }
  return in[ptr++];
}

void freef(FILE *f, const char *arg, i64 *result) {
  *result = 0;
  do {
    c = getChar(f);
  } while (!isdigit(c));
  do {
    *result = (*result << 3) + (*result << 1) + c - '0';
    c = getChar(f);
  } while (isdigit(c));
}

/** Cauta valoarea "x". **/
int find(i64 x) {
  int pos;
  i64 h = x % MOD;

  for (pos = hash[h]; (pos != 0) && (map[pos].v != x); pos = map[pos].next);
  return pos;
}

/** Adauga valoarea "x". **/
void insert(i64 x) {
  int h = x % MOD;

  map[++buff].v = x;
  map[buff].next = hash[h];
  hash[h] = buff;
}

int main(void) {
  int i;
  i64 Q, x;
  FILE *f = fopen("dtcsu.in", "r");

  /* Citirea datelor. */
  for (i = 0; i < Nadejde; i++) {
    freef(f, "%lld", &x);
    if (x % 2) {
      insert(x);
    }
  }

  /* Raspunde la intrebari. */
  int count = 0;
  for (freef(f, "%lld", &Q); Q; Q--) {
    freef(f, "%lld", &x);
    if ((x != 0) && (find(x / (x & -x)))) {
      count++;
    }
  }

  /* Afisarea solutiei. */
  freopen("dtcsu.out", "w", stdout);
  fprintf(stdout, "%d\n", count);
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}