4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <functional> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: #include <cassert> 4fd800b3a8 2011-02-23 kinaba: #include <cstring> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: typedef complex<double> CMP; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class BalancingAct { public: 4fd800b3a8 2011-02-23 kinaba: vector <string> recover(vector <int> labeled, vector <int> unlabeled) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: vector<int> same(unlabeled.size()); 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<same.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: same[i] = count(unlabeled.begin(), unlabeled.end(), unlabeled[i]); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: set<unsigned int> canBeMade; 4fd800b3a8 2011-02-23 kinaba: canBeMade.insert(0); 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<labeled.size(); ++i) { 4fd800b3a8 2011-02-23 kinaba: set<unsigned int> next; 4fd800b3a8 2011-02-23 kinaba: for(set<unsigned int>::iterator it=canBeMade.begin(); it!=canBeMade.end(); ++it) { 4fd800b3a8 2011-02-23 kinaba: if(*it+labeled[i] > *it ) 4fd800b3a8 2011-02-23 kinaba: next.insert(*it+labeled[i]); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: canBeMade.insert(next.begin(), next.end()); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: vector<unsigned int> cbm(canBeMade.begin(), canBeMade.end()); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<string> answer(unlabeled.size(), "no"); 4fd800b3a8 2011-02-23 kinaba: for(;;) { 4fd800b3a8 2011-02-23 kinaba: bool updated = false; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<unlabeled.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: if( answer[i] == "no" ) { 4fd800b3a8 2011-02-23 kinaba: unsigned int ul = unlabeled[i]; 4fd800b3a8 2011-02-23 kinaba: bool ok = false; 4fd800b3a8 2011-02-23 kinaba: if( canMake(ul, cbm) ) 4fd800b3a8 2011-02-23 kinaba: ok = true; 4fd800b3a8 2011-02-23 kinaba: else if( canMake(ul+1, cbm) && canMake(ul-1, cbm) ) 4fd800b3a8 2011-02-23 kinaba: ok = true; 4fd800b3a8 2011-02-23 kinaba: else if( same[i]>=2 ) { 4fd800b3a8 2011-02-23 kinaba: for(int k=2; k<=same[i]; ++k) { 4fd800b3a8 2011-02-23 kinaba: if(canMake(ul*k, cbm)) 4fd800b3a8 2011-02-23 kinaba: {ok=true; break;} 4fd800b3a8 2011-02-23 kinaba: bool lok = false, rok=false; 4fd800b3a8 2011-02-23 kinaba: for(int j=1; j<=k; ++j) { 4fd800b3a8 2011-02-23 kinaba: if(canMake(ul*k-j, cbm)) 4fd800b3a8 2011-02-23 kinaba: lok=true; 4fd800b3a8 2011-02-23 kinaba: if(canMake(ul*k+j, cbm)) 4fd800b3a8 2011-02-23 kinaba: rok=true; 4fd800b3a8 2011-02-23 kinaba: if(lok&&rok){ok=true; break;} 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: if( ok ) { 4fd800b3a8 2011-02-23 kinaba: // update 4fd800b3a8 2011-02-23 kinaba: updated = true; 4fd800b3a8 2011-02-23 kinaba: answer[i] = "yes"; 4fd800b3a8 2011-02-23 kinaba: for(int k=0,ke=cbm.size(); k!=ke; ++k) 4fd800b3a8 2011-02-23 kinaba: cbm.push_back(cbm[k]+unlabeled[i]); 4fd800b3a8 2011-02-23 kinaba: sort(cbm.begin(), cbm.end()); 4fd800b3a8 2011-02-23 kinaba: cbm.erase(unique(cbm.begin(),cbm.end()), cbm.end()); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: if( !updated ) 4fd800b3a8 2011-02-23 kinaba: break; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return answer; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: bool canMake( int t, vector<unsigned int>& cbm ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( t==0 || t==100000001 ) 4fd800b3a8 2011-02-23 kinaba: return true; 4fd800b3a8 2011-02-23 kinaba: if( binary_search(cbm.begin(), cbm.end(), t) ) 4fd800b3a8 2011-02-23 kinaba: return true; 4fd800b3a8 2011-02-23 kinaba: for(vector<unsigned int>::iterator it=cbm.begin(); it!=cbm.end(); ++it) 4fd800b3a8 2011-02-23 kinaba: if( binary_search(cbm.begin(), cbm.end(), t+*it) ) 4fd800b3a8 2011-02-23 kinaba: return true; 4fd800b3a8 2011-02-23 kinaba: return false; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: #include <ctime> 4fd800b3a8 2011-02-23 kinaba: double start_time; string timer() 4fd800b3a8 2011-02-23 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 4fd800b3a8 2011-02-23 kinaba: { os << "{ "; 4fd800b3a8 2011-02-23 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 4fd800b3a8 2011-02-23 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 4fd800b3a8 2011-02-23 kinaba: void verify_case(const vector <string>& Expected, const vector <string>& Received) { 4fd800b3a8 2011-02-23 kinaba: bool ok = (Expected == Received); 4fd800b3a8 2011-02-23 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 4fd800b3a8 2011-02-23 kinaba: cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } 4fd800b3a8 2011-02-23 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 4fd800b3a8 2011-02-23 kinaba: #define END verify_case(_, BalancingAct().recover(labeled, unlabeled));} 4fd800b3a8 2011-02-23 kinaba: int main(){ 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: CASE(0) 4fd800b3a8 2011-02-23 kinaba: int labeled_[] = {9,13,15,16}; 4fd800b3a8 2011-02-23 kinaba: vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 4fd800b3a8 2011-02-23 kinaba: int unlabeled_[] = {19}; 4fd800b3a8 2011-02-23 kinaba: vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 4fd800b3a8 2011-02-23 kinaba: string __[] = {"yes" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(1) 4fd800b3a8 2011-02-23 kinaba: int labeled_[] = {20}; 4fd800b3a8 2011-02-23 kinaba: vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 4fd800b3a8 2011-02-23 kinaba: int unlabeled_[] = {10,10}; 4fd800b3a8 2011-02-23 kinaba: vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 4fd800b3a8 2011-02-23 kinaba: string __[] = {"yes", "yes" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(2) 4fd800b3a8 2011-02-23 kinaba: int labeled_[] = {33333332,33333334}; 4fd800b3a8 2011-02-23 kinaba: vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 4fd800b3a8 2011-02-23 kinaba: int unlabeled_[] = {33333333,73,100000000}; 4fd800b3a8 2011-02-23 kinaba: vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 4fd800b3a8 2011-02-23 kinaba: string __[] = {"yes", "no", "yes" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(3) 4fd800b3a8 2011-02-23 kinaba: int labeled_[] = {12}; 4fd800b3a8 2011-02-23 kinaba: vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 4fd800b3a8 2011-02-23 kinaba: int unlabeled_[] = {1,1,2,2}; 4fd800b3a8 2011-02-23 kinaba: vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 4fd800b3a8 2011-02-23 kinaba: string __[] = {"yes", "yes", "yes", "yes" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(4) 4fd800b3a8 2011-02-23 kinaba: int labeled_[] = {31415926,5358979,32384626,43383279,50288419, 4fd800b3a8 2011-02-23 kinaba: 71693993,75105820,9749445,92307816,40628620, 4fd800b3a8 2011-02-23 kinaba: 89986280,34825342,11706798,21480865,13282306}; 4fd800b3a8 2011-02-23 kinaba: vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 4fd800b3a8 2011-02-23 kinaba: int unlabeled_[] = {64709384,46095505,82231725,35940812}; 4fd800b3a8 2011-02-23 kinaba: vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 4fd800b3a8 2011-02-23 kinaba: string __[] = {"no", "no", "no", "no" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(5) 4fd800b3a8 2011-02-23 kinaba: int labeled_[] = {1,2,4,8,16,32,64,128,256,512,1024,2048*1,2048*2,2048*4,2048*8,2048*16,2048*32,2048*64,2048*128,2048*256}; 4fd800b3a8 2011-02-23 kinaba: vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 4fd800b3a8 2011-02-23 kinaba: int unlabeled_[] = {999, 888, 777, 666}; 4fd800b3a8 2011-02-23 kinaba: vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 4fd800b3a8 2011-02-23 kinaba: string __[] = {"yes","yes","yes","yes"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: /* 4fd800b3a8 2011-02-23 kinaba: CASE(6) 4fd800b3a8 2011-02-23 kinaba: int labeled_[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 4fd800b3a8 2011-02-23 kinaba: int unlabeled_[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 4fd800b3a8 2011-02-23 kinaba: string __[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: */ 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE