2018/round2/replay_value.cpp

// Replay Value
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 52
#define MOD 1000000007

int dyn[2][LIM][LIM][LIM][LIM];
// dyn[i][a][b][c][d] = number of ways such that:
//   i = laser index
//   a = lowest Up
//   b = highest Down
//   c = lowest Right in regions 1/2
//   d = highest Right in region 3

int N;
vector<int> cy;

void ReadY(int &y)
{
	Read(y),cy.pb(y);
}

void CompY(int &y)
{
	y=lower_bound(All(cy),y)-cy.begin();
}

void Flip(int &v)
{
	v=N+1-v;
}

void Add(int &a,int b)
{
	a+=b;
		if (a>=MOD)
			a-=MOD;
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int YA,YB;
	int i,a,b,c,d,y,r,v,m,ans;
	int A,B;
	PR P[LIM];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// init
			cy.clear();
			// input
			Read(N),ReadY(YA),ReadY(YB);
				Fox(i,N)
					Read(P[i].x),ReadY(P[i].y);
			// compress y-coordinates
			sort(All(cy));
			CompY(YA),CompY(YB);
				Fox(i,N)
					CompY(P[i].y);
			// mirror y-axis such that B is below A
				if (YA<YB)
				{
					Flip(YA),Flip(YB);
						Fox(i,N)
							Flip(P[i].y);
				}
			// sort lasers by increasing x
			sort(P,P+N);
			// DP
			Fill(dyn,0);
			A=0,B=1;
			dyn[B][N+1][0][N+1][0]=1;
				Fox(i,N)
				{
					// slide DP window
					swap(A,B);
					Fill(dyn[B],0);
					// compute laser's region
					y=P[i].y;
					r=(y>YA ? 1 : (y>YB ? 2 : 3));
					// perform transitions
						Fox(a,N+2)
							Fox(b,N+2)
								Fox(c,N+2)
									Fox(d,N+2)
										if (v=dyn[A][a][b][c][d])
										{
											// up
												if (y>=d)
													Add(dyn[B][min(a,y)][b][c][d],v);
											// down
												if (y<=c)
													Add(dyn[B][a][max(b,y)][c][d],v);
											// left
												if ((r==1 && y>=b) || (r>1 && y<=a))
													Add(dyn[B][a][b][c][d],v);
											// right
												if (r<3)
													Add(dyn[B][a][b][min(c,y)][d],v);
												else
													Add(dyn[B][a][b][c][max(d,y)],v);
										}
				}
			// compute answer
			ans=1;
				Fox(i,N)
					ans=(LL)ans*4%MOD;
			v=0;
				Fox(a,N+2)
					Fox(b,N+2)
						Fox(c,N+2)
							Fox(d,N+2)
								Add(v,dyn[B][a][b][c][d]);
			ans=(ans-v+MOD)%MOD;
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}