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