085e72a21b 2011-07-09 kinaba: #include <iostream> 085e72a21b 2011-07-09 kinaba: #include <sstream> 085e72a21b 2011-07-09 kinaba: #include <iomanip> 085e72a21b 2011-07-09 kinaba: #include <vector> 085e72a21b 2011-07-09 kinaba: #include <string> 085e72a21b 2011-07-09 kinaba: #include <map> 085e72a21b 2011-07-09 kinaba: #include <set> 085e72a21b 2011-07-09 kinaba: #include <algorithm> 085e72a21b 2011-07-09 kinaba: #include <numeric> 085e72a21b 2011-07-09 kinaba: #include <iterator> 085e72a21b 2011-07-09 kinaba: #include <functional> 085e72a21b 2011-07-09 kinaba: #include <complex> 085e72a21b 2011-07-09 kinaba: #include <queue> 085e72a21b 2011-07-09 kinaba: #include <stack> 085e72a21b 2011-07-09 kinaba: #include <cmath> 085e72a21b 2011-07-09 kinaba: #include <cassert> 085e72a21b 2011-07-09 kinaba: #include <cstring> 085e72a21b 2011-07-09 kinaba: using namespace std; 085e72a21b 2011-07-09 kinaba: typedef long long LL; 085e72a21b 2011-07-09 kinaba: typedef complex<double> CMP; 085e72a21b 2011-07-09 kinaba: 085e72a21b 2011-07-09 kinaba: class Zoo { public: 085e72a21b 2011-07-09 kinaba: long long theCount(vector <int> answers) 085e72a21b 2011-07-09 kinaba: { 085e72a21b 2011-07-09 kinaba: map<int,int> nc; 085e72a21b 2011-07-09 kinaba: for(int i=0; i<answers.size(); ++i) 085e72a21b 2011-07-09 kinaba: nc[answers[i]] ++; 085e72a21b 2011-07-09 kinaba: 085e72a21b 2011-07-09 kinaba: int two = 0; 085e72a21b 2011-07-09 kinaba: int one = 0; 085e72a21b 2011-07-09 kinaba: for(int k=0 ;; ++k) 085e72a21b 2011-07-09 kinaba: if( nc[k] == 2 ) 085e72a21b 2011-07-09 kinaba: two++; 085e72a21b 2011-07-09 kinaba: else if( nc[k] == 1 ) 085e72a21b 2011-07-09 kinaba: { 085e72a21b 2011-07-09 kinaba: for(;; ++k) 085e72a21b 2011-07-09 kinaba: if( nc[k] == 1 ) 085e72a21b 2011-07-09 kinaba: one++; 085e72a21b 2011-07-09 kinaba: else if( nc[k] == 0 ) 085e72a21b 2011-07-09 kinaba: break; 085e72a21b 2011-07-09 kinaba: else 085e72a21b 2011-07-09 kinaba: return 0LL; 085e72a21b 2011-07-09 kinaba: break; 085e72a21b 2011-07-09 kinaba: } 085e72a21b 2011-07-09 kinaba: else if( nc[k] == 0 ) 085e72a21b 2011-07-09 kinaba: break; 085e72a21b 2011-07-09 kinaba: else 085e72a21b 2011-07-09 kinaba: return 0LL; 085e72a21b 2011-07-09 kinaba: if( two*2 + one != answers.size() ) 085e72a21b 2011-07-09 kinaba: return 0LL; 085e72a21b 2011-07-09 kinaba: LL r = 2; 085e72a21b 2011-07-09 kinaba: for(int i=0; i<two; ++i) 085e72a21b 2011-07-09 kinaba: r = r*2; 085e72a21b 2011-07-09 kinaba: return r; 085e72a21b 2011-07-09 kinaba: } 085e72a21b 2011-07-09 kinaba: }; 085e72a21b 2011-07-09 kinaba: 085e72a21b 2011-07-09 kinaba: // BEGIN CUT HERE 085e72a21b 2011-07-09 kinaba: #include <ctime> 085e72a21b 2011-07-09 kinaba: double start_time; string timer() 085e72a21b 2011-07-09 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 085e72a21b 2011-07-09 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 085e72a21b 2011-07-09 kinaba: { os << "{ "; 085e72a21b 2011-07-09 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 085e72a21b 2011-07-09 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 085e72a21b 2011-07-09 kinaba: void verify_case(const long long& Expected, const long long& Received) { 085e72a21b 2011-07-09 kinaba: bool ok = (Expected == Received); 085e72a21b 2011-07-09 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 085e72a21b 2011-07-09 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 085e72a21b 2011-07-09 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 085e72a21b 2011-07-09 kinaba: #define END verify_case(_, Zoo().theCount(answers));} 085e72a21b 2011-07-09 kinaba: int main(){ 085e72a21b 2011-07-09 kinaba: 085e72a21b 2011-07-09 kinaba: CASE(0) 085e72a21b 2011-07-09 kinaba: int answers_[] = {0, 1, 2, 3, 4}; 085e72a21b 2011-07-09 kinaba: vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 085e72a21b 2011-07-09 kinaba: long long _ = 2LL; 085e72a21b 2011-07-09 kinaba: END 085e72a21b 2011-07-09 kinaba: CASE(1) 085e72a21b 2011-07-09 kinaba: int answers_[] = {5, 8}; 085e72a21b 2011-07-09 kinaba: vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 085e72a21b 2011-07-09 kinaba: long long _ = 0LL; 085e72a21b 2011-07-09 kinaba: END 085e72a21b 2011-07-09 kinaba: CASE(2) 085e72a21b 2011-07-09 kinaba: int answers_[] = {0, 0, 0, 0, 0, 0}; 085e72a21b 2011-07-09 kinaba: vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 085e72a21b 2011-07-09 kinaba: long long _ = 0LL; 085e72a21b 2011-07-09 kinaba: END 085e72a21b 2011-07-09 kinaba: CASE(3) 085e72a21b 2011-07-09 kinaba: int answers_[] = {1, 0, 2, 0, 1}; 085e72a21b 2011-07-09 kinaba: vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 085e72a21b 2011-07-09 kinaba: long long _ = 8LL; 085e72a21b 2011-07-09 kinaba: END 085e72a21b 2011-07-09 kinaba: CASE(4) 085e72a21b 2011-07-09 kinaba: int answers_[] = {1, 0, 1}; 085e72a21b 2011-07-09 kinaba: vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 085e72a21b 2011-07-09 kinaba: long long _ = 0LL; 085e72a21b 2011-07-09 kinaba: END 085e72a21b 2011-07-09 kinaba: /* 085e72a21b 2011-07-09 kinaba: CASE(5) 085e72a21b 2011-07-09 kinaba: int answers_[] = ; 085e72a21b 2011-07-09 kinaba: vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 085e72a21b 2011-07-09 kinaba: long long _ = LL; 085e72a21b 2011-07-09 kinaba: END 085e72a21b 2011-07-09 kinaba: CASE(6) 085e72a21b 2011-07-09 kinaba: int answers_[] = ; 085e72a21b 2011-07-09 kinaba: vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 085e72a21b 2011-07-09 kinaba: long long _ = LL; 085e72a21b 2011-07-09 kinaba: END 085e72a21b 2011-07-09 kinaba: */ 085e72a21b 2011-07-09 kinaba: } 085e72a21b 2011-07-09 kinaba: // END CUT HERE