Artifact Content
Not logged in

Artifact 4557c7ca92985007fa4cc9a1ae5a582bcb2c0345


#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>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<LD> CMP;

static const unsigned MODVAL = 1000000009;

class Mountains { public:
	int countPlacements(vector <int> heights, vector <string> visibility)
	{
		int W = visibility[0].size();
		int N = visibility.size();
		memo.resize(N);

		vector<int> view(W, 0);
		return rec(W, view, heights.size()-1, heights, visibility);
	}

	vector< map<vector<int>,int> > memo;
	int rec(int W, const vector<int>& view, int i, vector<int>& H, const vector<string>& V)
	{
		if(i < 0)
			return 1;

		if(memo[i].count(view))
			return memo[i][view];

		int mustL=0, mustR=W-1;
		int mustNotL=W, mustNotR=-1;
		for(int x=0; x<W; ++x)
		{
			int LLL = x - (H[i]-view[x]-1);
			int RRR = x + (H[i]-view[x]-1);
			if(V[i][x] == 'X') {
				if( H[i] <= view[x] )
					return 0;
				mustL = max(mustL, LLL);
				mustR = min(mustR, RRR);
			} else {
//				if( H[i] > view[x] ) {
//					mustNotL = min(mustNotL, LLL);
//					mustNotR = max(mustNotR, RRR);
//				}
			}
		}

		LL result = 0;
		for(int c=mustL; c<=mustR; ++c) if(c<mustNotL || mustNotR<c)
		{
			bool good = true;
			for(int x=0; x<W && good; ++x) {
				int my_h = H[i] - abs(x-c);
				if((V[i][x]=='X') != (view[x] < my_h))
					good = false;
			}

			if( good ) {
				vector<int> view2(W);
				for(int x=0; x<W; ++x) {
					int my_h = H[i] - abs(x-c);
					view2[x] = max(my_h, view[x]);
				}
				result += rec(W, view2, i-1, H, V);
			}
		}
		return memo[i][view] = int(result % MODVAL);
	}
};

// 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 int& Expected, const 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(_, Mountains().countPlacements(heights, visibility));}
int main(){

CASE(0)
	int heights_[] = {2, 3, 2};
	  vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 
	string visibility_[] = {"------",
 "XXXX--",
 "---XXX"};
	  vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_)); 
	int _ = 4; 
END
CASE(1)
	int heights_[] = {4, 3, 4};
	  vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 
	string visibility_[] = {"XXXXX--------",
 "----------XXX",
 "----XXXXXXX--"};
	  vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_)); 
	int _ = 4; 
END
CASE(2)
	int heights_[] = {13, 2, 3, 2};
	  vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 
	string visibility_[] = {"XXXXXXXXX",
 "-XXX-----",
 "----XXXXX",
 "-----XXX-"};
	  vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_)); 
	int _ = 9; 
END
CASE(3)
	int heights_[] = {8, 2, 9, 3, 10};
	  vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 
	string visibility_[] = {"X------",
 "-------",
 "------X",
 "-------",
 "XXXXXXX"};
	  vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_)); 
	int _ = 98; 
END
CASE(4)
	int heights_[] = {20, 20, 20, 20, 20, 20, 45, 50, 49, 50};
	  vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 
	string visibility_[] = {"-------------------",
 "-------------------",
 "-------------------",
 "-------------------",
 "-------------------",
 "-------------------",
 "-------------------",
 "------------XXXXXXX",
 "XXXXXXX------------",
 "XXXXXXXXXXXXXXXXXXX"}
;
	  vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_)); 
	int _ = 973726691; 
END
CASE(5)
	int heights_[] = {20, 20, 20, 20, 20, 20, 45, 50, 49, 50};
	  vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 
	string visibility_[] = {"-------------------------------------------------",
 "-------------------------------------------------",
 "-------------------------------------------------",
 "-------------------------------------------------",
 "-------------------------------------------------",
 "-------------------------------------------------",
 "-------------------------------------------------",
 "------------XXXXXXX------------------------------",
 "XXXXXXX------------------------------------------",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}
;
	  vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_)); 
	int _ = -1; 
END
}
// END CUT HERE