Artifact Content
Not logged in

Artifact 65c638c38947b4738128eaed6a3788eda8763ebd


#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 = 1000000007;

class WolfInZooDivOne { public:
	int count(int N, vector <string> L_, vector <string> R_)
	{
		vector<int> L, R;
		{
			stringstream sin(accumulate(L_.begin(), L_.end(), string()));
			for(int s; sin>>s;) L.push_back(s);
		}
		{
			stringstream sin(accumulate(R_.begin(), R_.end(), string()));
			for(int s; sin>>s;) R.push_back(s+1);
		}

		set< pair<int,int> > LR;
		for(int i=0; i<L.size(); ++i)
			LR.insert(make_pair(L[i], R[i]));

		vector< pair<int,int> > LR_imp;
		for(set< pair<int,int> >::iterator it=LR.begin(); it!=LR.end(); ++it) {
			bool important = true;
			for(set< pair<int,int> >::iterator kt=LR.begin(); kt!=LR.end(); ++kt)
				if(it != kt && kt->first<=it->first && it->second<=kt->second)
					important = false;
			if(important)
				LR_imp.push_back(*it);
		}

		return solve(N, LR_imp);
	}

	int solve(int N, const vector< pair<int,int> >& LR)
	{
		memo = vector<vector<vector<int> > >(N,
			vector<vector<int> >(LR.size()+1, vector<int>(LR.size()+1, -1)));
		return rec(0, N, LR, 0, 0, 0, 0);
	}

	vector<vector<vector<int> > > memo;
	int rec(int i, const int N, const vector< pair<int,int> >& LR, int end_of_past, int end_of_two, int end_of_one,
		int end_of_zero)
	{
		if(i == N)
			return 1;
		int& me = memo[i][end_of_two][end_of_one];
		if(me != -1)
			return me;

		int ez = end_of_zero;
		while(ez<LR.size() && LR[ez].first<=i)
			++ez;
		int ep = end_of_past;
		while(ep<ez && LR[ep].second<=i)
			++ep;

		// do not place wolf at i.
		int total = rec(i+1, N, LR, ep, max(ep,end_of_two), max(ep,end_of_one), ez);

		// place wolf at i.
		if(ep >= end_of_two) {
			int e1 = max(ep, end_of_one);
			int e2 = max(ep, end_of_two);
			while(e2<e1 && i<LR[e2].second)
				++e2;
			while(e1<ez && i<LR[e1].second)
				++e1;
			total += rec(i+1, N, LR, ep, e2, e1, ez);
		}
		return me = (total % 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(_, WolfInZooDivOne().count(N, L, R));}
int main(){

CASE(0)
	int N = 5; 
	string L_[] = {"0"};
	  vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); 
	string R_[] = {"4"};
	  vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
	int _ = 16; 
END
CASE(1)
	int N = 5; 
	string L_[] = {"0 1"};
	  vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); 
	string R_[] = {"2 4"};
	  vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
	int _ = 21; 
END
CASE(2)
	int N = 10; 
	string L_[] = {"0 4 2 7"};
	  vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); 
	string R_[] = {"3 9 5 9"};
	  vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
	int _ = 225; 
END
CASE(3)
	int N = 100; 
	string L_[] = {"0 2 2 7 10 1","3 16 22 30 33 38"," 42 44 49 51 57 60 62"," 65 69 72 74 77 7","8 81 84 88 91 93 96"};
	  vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); 
	string R_[] = {"41 5 13 22 12 13 ","33 41 80 47 40 ","4","8 96 57 66 ","80 60 71 79"," 70 77 ","99"," 83 85 93 88 89 97 97 98"};
	  vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
	int _ = 6419882; 
END
/*
CASE(4)
	int N = ; 
	string L_[] = ;
	  vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); 
	string R_[] = ;
	  vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
	int _ = ; 
END
CASE(5)
	int N = ; 
	string L_[] = ;
	  vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); 
	string R_[] = ;
	  vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
	int _ = ; 
END
*/
}
// END CUT HERE