SRM 511 Div1 Easy Div2 Medium Zoo

問題

動物園にうさぎと猫が合計N匹いて,どの2匹をとっても背の高さが違う.Fox Jiroは両者の区別がつかないので各動物に次のような質問をした,「自分よりも背の高い同じ動物は何匹いますか?」.
N個の回答があった場合,解答を行った動物のうさぎと猫の可能な組み合わせ数を考えよ.

解答

全員が嘘を言わず,正確に答えた場合,必ず0と答えるような動物が存在する.もし,0と答えるような動物が1匹の場合,猫かうさぎの1種類しかいない,2匹の場合は必ず2種類,それ以上の場合はだれかが嘘を付いている.答えがxと答える場合,同様の考えができる.直感的に考えてxと答える動物の数がx-1と答える動物の数を超えてしまうとおかしい.つまり0〜n-1と答えた動物の数を並べた場合,値が0〜2であり,単調非増加でなければいけない.
xと答えた動物の数が2の場合,どちらについてもうさぎ,猫の両方の割り当てが可能.また先頭から値を読み,初めて動物の数が1となる答えをyとすると,この時もうさぎ,猫の両方の割り当てが可能.しかし,それ以降y以上と答えた動物に関しては必ずyと同じ動物にならなければいけない.
A = 2の数 ,もし1の数があれば+1した時2^Aが答えとなる.

class Zoo
{
public:
  long long theCount(vector <int> answers)
    {
      int n = answers.size();
      vector<int> rank(n, 0);
      int i;
      for(i = 0; i < n; i++){
        if (answers[i] >= n) return 0;
        rank[answers[i]]++;
      }
      // for(i = 0; i < n; i++){
      //   cout << "i=" << i << " rank[i]=" << rank[i] << endl;
      // }
      if (rank[0] == 0 || rank[0] > 2) return 0;
      long long ret = 2;
      bool first = true;
      if (rank[0] == 1) first = false;
      for(i = 1; i < n; i++){
        if (rank[i] > 2 || rank[i] > rank[i-1]) return 0;
        if (rank[i] == 2)ret *= 2;
        if (first && rank[i] == 1) {
          ret *= 2;
          first = false;
        }
        // if (rank[i] == 0) break;
      }
      return ret;
    }
};