Artifact Content
Not logged in

Artifact 65aad8bb5e7b3849b0fa65cb5921dd6f58bfa850


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

class BalancingAct { public:
	vector <string> recover(vector <int> labeled, vector <int> unlabeled) 
	{
		vector<int> same(unlabeled.size());
		for(int i=0; i<same.size(); ++i)
			same[i] = count(unlabeled.begin(), unlabeled.end(), unlabeled[i]);

		set<unsigned int> canBeMade;
		canBeMade.insert(0);
		for(int i=0; i<labeled.size(); ++i) {
			set<unsigned int> next;
			for(set<unsigned int>::iterator it=canBeMade.begin(); it!=canBeMade.end(); ++it) {
				if(*it+labeled[i] > *it )
					next.insert(*it+labeled[i]);
			}
			canBeMade.insert(next.begin(), next.end());
		}
		vector<unsigned int> cbm(canBeMade.begin(), canBeMade.end());

		vector<string> answer(unlabeled.size(), "no");
		for(;;) {
			bool updated = false;
			for(int i=0; i<unlabeled.size(); ++i)
				if( answer[i] == "no" ) {
					unsigned int ul = unlabeled[i];
					bool ok = false;
					if( canMake(ul, cbm) )
						ok = true;
					else if( canMake(ul+1, cbm) && canMake(ul-1, cbm) )
						ok = true;
					else if( same[i]>=2 ) {
						for(int k=2; k<=same[i]; ++k) {
							if(canMake(ul*k, cbm))
								{ok=true; break;}
							bool lok = false, rok=false;
							for(int j=1; j<=k; ++j) {
								if(canMake(ul*k-j, cbm))
									lok=true;
								if(canMake(ul*k+j, cbm))
									rok=true;
								if(lok&&rok){ok=true; break;}
							}
						}
					}

					if( ok ) {
						// update
						updated = true;
						answer[i] = "yes";
						for(int k=0,ke=cbm.size(); k!=ke; ++k)
							cbm.push_back(cbm[k]+unlabeled[i]);
						sort(cbm.begin(), cbm.end());
						cbm.erase(unique(cbm.begin(),cbm.end()), cbm.end());
					}
				}
			if( !updated )
				break;
		}
		return answer;
	}

	bool canMake( int t, vector<unsigned int>& cbm )
	{
		if( t==0 || t==100000001 )
			return true;
		if( binary_search(cbm.begin(), cbm.end(), t) )
			return true;
		for(vector<unsigned int>::iterator it=cbm.begin(); it!=cbm.end(); ++it)
			if( binary_search(cbm.begin(), cbm.end(), t+*it) )
				return true;
		return false;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const vector <string>& Expected, const vector <string>& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, BalancingAct().recover(labeled, unlabeled));}
int main(){

CASE(0)
	int labeled_[] = {9,13,15,16};
	  vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 
	int unlabeled_[] = {19};
	  vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 
	string __[] = {"yes" };
	  vector <string> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(1)
	int labeled_[] = {20};
	  vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 
	int unlabeled_[] = {10,10};
	  vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 
	string __[] = {"yes", "yes" };
	  vector <string> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(2)
	int labeled_[] = {33333332,33333334};
	  vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 
	int unlabeled_[] = {33333333,73,100000000};
	  vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 
	string __[] = {"yes", "no", "yes" };
	  vector <string> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(3)
	int labeled_[] = {12};
	  vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 
	int unlabeled_[] = {1,1,2,2};
	  vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 
	string __[] = {"yes", "yes", "yes", "yes" };
	  vector <string> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(4)
	int labeled_[] = {31415926,5358979,32384626,43383279,50288419,
71693993,75105820,9749445,92307816,40628620,
89986280,34825342,11706798,21480865,13282306};
	  vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 
	int unlabeled_[] = {64709384,46095505,82231725,35940812};
	  vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 
	string __[] = {"no", "no", "no", "no" };
	  vector <string> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(5)
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};
	  vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 
	  int unlabeled_[] = {999, 888, 777, 666};
	  vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 
	  string __[] = {"yes","yes","yes","yes"};
	  vector <string> _(__, __+sizeof(__)/sizeof(*__)); 
END
/*
CASE(6)
	int labeled_[] = ;
	  vector <int> labeled(labeled_, labeled_+sizeof(labeled_)/sizeof(*labeled_)); 
	int unlabeled_[] = ;
	  vector <int> unlabeled(unlabeled_, unlabeled_+sizeof(unlabeled_)/sizeof(*unlabeled_)); 
	string __[] = ;
	  vector <string> _(__, __+sizeof(__)/sizeof(*__)); 
END
*/
}
// END CUT HERE