SRM511 Div1 250

問題

動物園にNアニマルがいる．といってもウサギとネコの2種類しかいない．それぞれの種類において，彼らの身長はすべて異なる．

キツネのJiroはウサギとネコの見分けがつけられない(←！)．そこで，すべてのアニマルに「あなたと同じ種類のアニマルで，あなたより身長が高いのは何匹いる？」と聞いた．
その回答結果が与えられるので，全員が真実を話したと仮定した場合にウサギとネコの対応の組み合わせはいくつ存在するか．

例：
{0,1,2,3,4}
→{R,R,R,R,R}か{C,C,C,C,C}で2通り
{1,0,2,0,1}
→{R,R,R,C,C}や{C,R,C,C,R}など8通り

考え方

それぞれの数字の個数をカウントしておく(0が何個，1が何個．．．)．
それぞれが0から1ずつ増えていくようになっていないと矛盾するので，カウント結果が{2,2,2,...,1,1,....,1}のようになってないといけない．
そうなってない({0,0,2,2,1}や{2,2,1,2}など)ならばありえないので0．

もしそのようになってる場合は，2の部分はRかCで2通り，1の部分はそれ以降はRまたはCが連続していないといけない．2なら2通り，1が出たらそれ以降が同じのが並ぶので2通りで掛けつづけたものが答え．

ll ret = 1LL;
for(int i=0; i<=max_value; i++){
  if(cnt[i]==1){ //1がでたらそれ以降はRかCだけじゃないといけないので2通りかけて終了
    ret *= 2LL;
    break;
  }
  ret *= 2LL; //2の場合はRまたはCの組み合わせがあるので，2通りかけて次へ
}
return ret;