Cod sursa(job #1244951)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 18 octombrie 2014 14:15:38
Problema Balanta Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <fstream>

#include <set>
#include <vector>

struct Trial {
  std::set<int> left;
  std::set<int> right;
  int result;
};

bool could_be(const std::vector<Trial>& v, int coin) {
  bool seen_in_practice[3] = { false };
  for (int i = 0; i < v.size(); ++i) {
    // If neither side contains it, result should be 0.
    if (v[i].left.count(coin) == 0 &&
        v[i].right.count(coin) == 0 &&
        v[i].result != 0) {
      return false;
    }

    // If it is in the experiment, experiment can't be 0.
    if ((v[i].left.count(coin) || v[i].right.count(coin)) &&
        v[i].result == 0) {
      return false;
    }

    if (v[i].left.count(coin)) {
      seen_in_practice[v[i].result] = true;
    }
    if (v[i].right.count(coin)) {
      seen_in_practice[3 - v[i].result] = true;
    }
  }

  return seen_in_practice[1] ^ seen_in_practice[2];
}

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

  int n, m;
  in >> n >> m;
  std::vector<Trial> v;
  for (int i = 0; i < m; ++i) {
    Trial t;
    int coins;
    in >> coins;
    for (int j = 0; j < coins; ++j) {
      int k;
      in >> k;
      t.left.insert(k);
    }
    for (int j = 0; j < coins; ++j) {
      int k;
      in >> k;
      t.right.insert(k);
    }
    in >> t.result;
    v.push_back(t);
  }

  std::vector<int> candidates;
  for (int i = 1; i <= n; ++i) {
    if (could_be(v, i)) {
      candidates.push_back(i);
    }
  }

  out << (candidates.size() != 1 ? 0 : candidates[0]) << std::endl;

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

  return 0;
}