Cod sursa(job #2105497)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 13 ianuarie 2018 14:37:42
Problema Amlei Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 2e4 + 5e3;
#define MOD 131072

int a[MAXN], b[MAXN];

class Hash {
  public:
  int val[MAXN], next[MAXN], *list, k = 0;
  Hash() {
    list = new int[MOD];
    memset(list, 0x00, sizeof(list));
  }
  inline void insert(int x) {
    val[++k] = x;
    next[k] = list[x % MOD];
    list[x % MOD] = k;
  }
  inline bool find(int x) {
    int p = list[x % MOD];
    while (p && val[p] != x) {
      p = next[p];
    }
    return val[p] == x;
  }
  inline void clear() {
    memset(list, 0x00, sizeof(list));
    k = 0;
  }
} h1, h2;

static inline int max(int a, int b) {
  return a > b ? a : b;
} 

int main() {
  int n, t, u, k, x;
  FILE *fin = fopen("amlei.in", "r");
  FILE *fout = fopen("amlei.out", "w");
  while (fscanf(fin, "%d%d%d", &n, &t, &u) != EOF) {
    k = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < t; ++j) {
        fscanf(fin, "%d", &x);
        if (x > 0 && !h1.find(x)) {
          a[k++] = x;
          h1.insert(x);
        }
      }
    }
    std::sort(a, a + k);
    k = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < u; ++j) {
        fscanf(fin, "%d", &x);
        if (x > 0 && !h2.find(x)) {
          b[k++] = x;
          h2.insert(x);
        }
      }
    }
    std::sort(a, a + n * t);
    std::sort(b, b + n * u);
    n = max(n * t, n * u);
    k = 0;
    while (k < n && a[k] == b[k]) {
      ++k;
    }
    fprintf(fout, "%s\n", k == n ? "DA" : "NU");
    memset(a, 0x00, sizeof(a));
    memset(b, 0x00, sizeof(b));
    h1.clear();
    h2.clear();
  }
  fclose(fin);
  fclose(fout);
  return 0;
}