解いた問題

5/07/2012

SRM511 Div1 Easy

250

条件に合うように2つのグループに分ける。
あとは、割り当て方が何通りあるかを計算する。



class Zoo {
public:
  long long theCount(vector <int> ans)
  {
    vector<int> a, b;
    map<int, int> cnt;

    for (int i = 0; i < (int)ans.size(); ++i) {
      if (cnt[ans[i]]) b.push_back(ans[i]);
      else a.push_back(ans[i]);
      if (2 < ++cnt[ans[i]]) return 0;
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    for (int i = 0; i < (int)a.size(); ++i) {
      if (binary_search(a.begin(), a.end(), i)) ;
      else return 0;
    }

    for (int i = 0; i < (int)b.size(); ++i) {
      if (binary_search(b.begin(), b.end(), i)) ;
      else return 0;
    }

    if (a.empty() || b.empty()) return 2;

    lli ret = 1LL << (min(a.size(), b.size()) + (a.size() != b.size()));
    return ret;
  }
};