Cod sursa(job #1244919)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 18 octombrie 2014 13:42:50
Problema Amlei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <iostream>
#include <fstream>

#include <set>
#include <vector>

void read_formula(std::istream& in,
                  int nvar,
                  int nconj,
                  std::set<long long>* conjset) {
  conjset->clear();
  for (int i = 0; i < nconj; ++i) {
    std::vector<bool> seenpos(nvar, false);
    std::vector<bool> seenneg(nvar, false);
    int code = 0;
    for (int j = 0; j < nvar; ++j) {
      int var;
      in >> var;
      if (var > 0) {
        seenpos[var] = true;
      } else {
        seenpos[-var] = true;
      }
      if (var > 0) {
        code |= (1 << (var - 1));
      }
    }

    // If you've seen both positive and negative, give up.
    bool term_always_false = false;
    for (int j = 0; j < nvar; ++j) {
      if (seenpos[j] && seenneg[j]) {
        term_always_false = true;
        break;
      }
    }
    if (term_always_false) {
      continue;
    }

    // If there are terms we haven't seen, then we're not treating this case
    // atm.
    conjset->insert(code);
  }
}

bool same(const std::set<long long>& a,
          const std::set<long long>& b) {
  if (a.size() != b.size()) {
    return false;
  }
  std::set<long long>::iterator ita = a.begin();
  std::set<long long>::iterator itb = b.begin();
  while (ita != a.end() && itb != b.end()) {
    if (*ita != *itb) {
      return false;
    }
    ita++;
    itb++;
  }

  return true;
}

int main()
{
  std::ifstream in("amlei.in");
  std::ofstream out("amlei.out");

  int n, t, u;

  do {
    in >> n >> t >> u;

    if (!in.good()) {
      break;
    }

    std::set<long long> f1;
    std::set<long long> f2;
    read_formula(in, n, t, &f1);
    read_formula(in, n, u, &f2);

    out << (same(f1, f2) ? "DA" : "NU") << std::endl;
  } while (true);

  in.close();
  out.close();

  return 0;
}