Artifact Content
Not logged in

Artifact 5b1986066a8653988e2a84369ec7a8d12cb58954


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

int lsb(int x) {
	for(int i=0 ;; ++i)
		if(x&(1<<i))
			return i;
}


class BoardEscape { public:
	string findWinner(vector <string> s, int k)
	{
		const int H = s.size(), W = s[0].size();
		const int dy[] = {-1,+1,0,0};
		const int dx[] = {0,0,-1,+1};

		vector<vector<vector<int>>> G_history;
		for(int t=0; t<=256; ++t) {
			vector<vector<int>> G(H, vector<int>(W));
			for(int y=0; y<H; ++y)
			for(int x=0; x<W; ++x) if(s[y][x]!='#') {
				if(G_history.empty())
					G[y][x] = 0;
				else {
					if(s[y][x]=='E')
						G[y][x] = 0;
					else {
						int nf = 0xffffffff;
						for(int _=0; _<4; ++_) {
							int yy=y+dy[_], xx=x+dx[_];
							if(0<=yy&&yy<H&&0<=xx&&xx<W&&s[yy][xx]!='#')
								nf &= ~(1<<G_history.back()[yy][xx]);
						}
						G[y][x] = lsb(nf);
					}
				}
			}
			G_history.emplace_back(G);
		}

		int ans = 0;
		for(int y=0; y<H; ++y)
		for(int x=0; x<W; ++x) if(s[y][x]=='T') {
			if(k < G_history.size())
				ans ^= G_history[k][y][x];
			else
				ans ^= G_history[((k-1)%64)+193][y][x];
		}
		return (ans ? "Alice" : "Bob");
	}
};

// 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 string& Expected, const string& 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(_, BoardEscape().findWinner(s, k));}
int main(){
CASE(0)
	string s_[] = {"TE"};
	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 
	int k = 2; 
	string _ = "Alice"; 
END
CASE(1)
	string s_[] = {"E#E",
 "#T#",
 "E#E"};
	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 
	int k = 1000000; 
	string _ = "Bob"; 
END
CASE(2)
	string s_[] = {"T.T.T.",
 ".E.E.E"};
	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 
	int k = 1; 
	string _ = "Alice"; 
END
CASE(3)
	string s_[] = {"TTE"};
	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 
	int k = 6; 
	string _ = "Alice"; 
END
CASE(4)
	string s_[] = {"..........................",
 "......TTT..TTT..T...T.....",
 ".....T.....T..T.TT.TT.....",
 "......TTT..TTT..T.T.T.....",
 ".........T.T.T..T...T.....",
 "......TTT..T..T.T...T.....",
 "..........................",
 "...E#E#E#E#E#E#E#E#E#E#...",
 "..........................",
 "......TTT..TTT...TTT......",
 ".....T........T.T.........",
 "......TTT.....T..TTT......",
 ".....T...T...T..T...T.....",
 "......TTT....T...TTT......",
 "..........................",
 "...#E#E#E#E#E#E#E#E#E#E...",
 "..........................",
 "....TT...T...T..T.TTT.T...",
 "...T.....T...T..T.T...T...",
 "...T.TT..T...TTTT.TT..T...",
 "...T..T..T...T..T.T.......",
 "....TT...TTT.T..T.T...T...",
 ".........................."};
	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 
	int k = 987654321; 
	string _ = "Bob"; 
END
/*
CASE(5)
	string s_[] = ;
	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 
	int k = ; 
	string _ = ; 
END
CASE(6)
	string s_[] = ;
	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 
	int k = ; 
	string _ = ; 
END
*/
}
// END CUT HERE