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 <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: using namespace std;
4fd800b3a8 2011-02-23        kinaba: typedef long long LL;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: int N;
4fd800b3a8 2011-02-23        kinaba: vector<int> A;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: typedef int vert;
4fd800b3a8 2011-02-23        kinaba: typedef int cost;
4fd800b3a8 2011-02-23        kinaba: typedef pair<cost,vert> edge;
4fd800b3a8 2011-02-23        kinaba: typedef vector<edge>    edges;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: vector<int> dijkstra_like( vert S, int T, int I )
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	set<int> ans;
4fd800b3a8 2011-02-23        kinaba: 	for(int i=1; i<=I; ++i) ans.insert(i);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	priority_queue< edge, edges, greater<edge> > Q;
4fd800b3a8 2011-02-23        kinaba: 	Q.push( edge(0, S) );
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: //	set<vert> vis;
4fd800b3a8 2011-02-23        kinaba: 	vector<bool> vis(1<<24);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	while( !Q.empty() )
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		edge ce=Q.top(); Q.pop();
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		int  t = ce.first;
4fd800b3a8 2011-02-23        kinaba: 		vert v = ce.second;
4fd800b3a8 2011-02-23        kinaba: 		if( vis[v] )
4fd800b3a8 2011-02-23        kinaba: 			continue;
4fd800b3a8 2011-02-23        kinaba: 		vis[v]=true;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		int sw = v&511;
4fd800b3a8 2011-02-23        kinaba: 		int a[] = {(v>>9)&31, (v>>14)&31, (v>>19)&31};
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		ans.erase(sw);
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<(1<<N+1); ++i)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			int sw2 = sw;
4fd800b3a8 2011-02-23        kinaba: 			int a2[] = {a[0], a[1], a[2]};
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			int nzMin = 9999;
4fd800b3a8 2011-02-23        kinaba: 			for(int j=0; j<N; ++j) {
4fd800b3a8 2011-02-23        kinaba: 				if( (i&(1<<j)) )
4fd800b3a8 2011-02-23        kinaba: 					a2[j] = A[j]-a2[j];
4fd800b3a8 2011-02-23        kinaba: 				if( a2[j] )
4fd800b3a8 2011-02-23        kinaba: 					nzMin = min(nzMin, a2[j]);
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 			if( (i&(1<<N)) ) sw2 = 0;
4fd800b3a8 2011-02-23        kinaba: 			if( nzMin==9999 ) continue;
4fd800b3a8 2011-02-23        kinaba: 			if( t+nzMin > T )
4fd800b3a8 2011-02-23        kinaba: 				continue;
4fd800b3a8 2011-02-23        kinaba: 			for(int j=0; j<N; ++j)
4fd800b3a8 2011-02-23        kinaba: 				if( a2[j] )
4fd800b3a8 2011-02-23        kinaba: 					a2[j] -= nzMin;
4fd800b3a8 2011-02-23        kinaba: 			sw2 += nzMin;
4fd800b3a8 2011-02-23        kinaba: 			vert u = sw2 | (a2[0]<<9) | (a2[1]<<14) | (a2[2]<<19);
4fd800b3a8 2011-02-23        kinaba: 			if( !vis[u] ) {
4fd800b3a8 2011-02-23        kinaba: 				Q.push( edge(t+nzMin,u) );
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	return vector<int>(ans.begin(), ans.end());
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: class SandTimers
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: public:
4fd800b3a8 2011-02-23        kinaba: 	vector <int> badIntervals(vector <int> timers, int maxInterval, int maxTime)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		N = timers.size();
4fd800b3a8 2011-02-23        kinaba: 		A = timers;
4fd800b3a8 2011-02-23        kinaba: 		return dijkstra_like( vert(), maxTime, maxInterval );
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() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: int verify_case(const vector <int> &Expected, const vector <int> &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } return 0;}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<int N> struct Case_ { Case_(){start_time=clock();} };
4fd800b3a8 2011-02-23        kinaba: char Test_(...);
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<0>) {
4fd800b3a8 2011-02-23        kinaba: 	int timers_[] = { 5, 7 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
4fd800b3a8 2011-02-23        kinaba: 	int maxInterval = 10;
4fd800b3a8 2011-02-23        kinaba: 	int maxTime = 10;
4fd800b3a8 2011-02-23        kinaba: 	int RetVal_[] = {1, 6, 8 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<1>) {
4fd800b3a8 2011-02-23        kinaba: 	int timers_[] = { 2, 10, 20 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
4fd800b3a8 2011-02-23        kinaba: 	int maxInterval = 30;
4fd800b3a8 2011-02-23        kinaba: 	int maxTime = 40;
4fd800b3a8 2011-02-23        kinaba: 	int RetVal_[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<2>) {
4fd800b3a8 2011-02-23        kinaba: 	int timers_[] = { 2, 5, 9 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
4fd800b3a8 2011-02-23        kinaba: 	int maxInterval = 360;
4fd800b3a8 2011-02-23        kinaba: 	int maxTime = 360;
4fd800b3a8 2011-02-23        kinaba: 	vector <int> RetVal;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<3>) {
4fd800b3a8 2011-02-23        kinaba: 	int timers_[] = { 4 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
4fd800b3a8 2011-02-23        kinaba: 	int maxInterval = 23;
4fd800b3a8 2011-02-23        kinaba: 	int maxTime = 47;
4fd800b3a8 2011-02-23        kinaba: 	int RetVal_[] = {1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 18, 19, 21, 22, 23 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<4>) {
4fd800b3a8 2011-02-23        kinaba: 	int timers_[] = { 20, 13 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
4fd800b3a8 2011-02-23        kinaba: 	int maxInterval = 30;
4fd800b3a8 2011-02-23        kinaba: 	int maxTime = 30;
4fd800b3a8 2011-02-23        kinaba: 	int RetVal_[] = {1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 28, 29, 30 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<5>) {
4fd800b3a8 2011-02-23        kinaba: 	int timers_[] = { 20, 17, 13 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
4fd800b3a8 2011-02-23        kinaba: 	int maxInterval = 25;
4fd800b3a8 2011-02-23        kinaba: 	int maxTime = 30;
4fd800b3a8 2011-02-23        kinaba: 	int RetVal_[] = {18, 19 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<6>) {
4fd800b3a8 2011-02-23        kinaba: 	int timers_[] = { 20, 20, 19 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
4fd800b3a8 2011-02-23        kinaba: 	int maxInterval = 360;
4fd800b3a8 2011-02-23        kinaba: 	int maxTime = 360;
4fd800b3a8 2011-02-23        kinaba: 	vector <int> RetVal;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
4fd800b3a8 2011-02-23        kinaba: template<>      void Run_<-1>() {}
4fd800b3a8 2011-02-23        kinaba: int main() { Run_<0>(); }
4fd800b3a8 2011-02-23        kinaba: // END CUT HERE
4fd800b3a8 2011-02-23        kinaba: