Artifact Content
Not logged in

Artifact bec7920e12c18fbc89ee438ee06da4b2c0d580b8


#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 TheMoviesLevelTwoDivOne { public:
	vector <int> find(vector <int> length, vector <int> scary) 
	{
		int N = length.size();

		vector<int> lwb(N), inc(N);
		for(int i=0; i<N; ++i)
			if( scary[i]+47 < length[i] )
				lwb[i] = length[i] - 47;
			else
				lwb[i] = scary[i];
		for(int i=0; i<N; ++i)
			inc[i] = 47 - length[i];

		memo = vector<bool>(1<<N);
		memo[(1<<N)-1] = true;
		vector<int> temp;
		rec(0, 74, N, lwb, inc, temp);

		set<int> not_used;
		for(int i=0; i<N; ++i) not_used.insert(i);
		for(int i=0; i<result.size(); ++i)
			not_used.erase(result[i]);
		result.insert(result.end(), not_used.begin(), not_used.end());

		return result;
	}

	vector<int>  result;
	vector<bool> memo;
	void rec(int mask, int cur, int N, vector<int>& lwb, vector<int>& inc, vector<int>& temp)
	{
		if( result.size() < temp.size() )
			result = temp;
		if( memo[mask] )
			return;
		memo[mask] = true;

		for(int i=0; i<N; ++i)
			if( !(mask & (1<<i)) && cur>=lwb[i] )
			{
				temp.push_back(i);
				rec(mask|(1<<i), cur+inc[i], N, lwb, inc, temp);
				temp.pop_back();
			}
	}
};

// 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 <int>& Expected, const vector <int>& 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(_, TheMoviesLevelTwoDivOne().find(length, scary));}
int main(){

CASE(0)
	int length_[] = {100, 50};
	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_)); 
	int scary_[] = {1, 1};
	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_)); 
	int __[] = {0, 1 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(1)
	int length_[] = {100, 50};
	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_)); 
	int scary_[] = {1, 49};
	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_)); 
	int __[] = {1, 0 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(2)
	int length_[] = {100, 100, 100, 100};
	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_)); 
	int scary_[] = {77, 76, 75, 74};
	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_)); 
	int __[] = {3, 0, 1, 2 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(3)
	int length_[] = {100};
	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_)); 
	int scary_[] = {99};
	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_)); 
	int __[] = {0 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(4)
	int length_[] = {2};
	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_)); 
	int scary_[] = {1};
	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_)); 
	  int __[] = {0};
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(5)
	int length_[] = {3};
	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_)); 
	int scary_[] = {1};
	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_)); 
	  int __[] = {0};
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(6)
  int length_[] = {5,6,7,8,9,10,11,10,9,8,7,6,5,6,7,8,9,10,11,10};
	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_)); 
  int scary_[] = {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3};
	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_)); 
  int __[] = {-1};
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(7)
  int length_[] = {185, 53, 28, 92, 70};
	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_)); 
  int scary_[] = {96, 17, 4, 6, 34};
	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_)); 
  int __[] = {1,2,3,4,0};
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
}
// END CUT HERE