Submission #42115561

---

Source Code Expand

#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int N = 10;
int n;
string st[N];
struct Surreal {
	ll n;
	int d;
	Surreal(ll _n = 0, int _d = 0) { n = _n, d = _d; }
	inline friend Surreal operator + (const Surreal &x, const Surreal &y) {
		int mx = max(x.d, y.d);
		ll t = (x.n << (mx - x.d)) + (y.n << (mx - y.d));
		int v = min(mx, __builtin_ctzll(t));
		mx -= v;
		t >>= v;
		return Surreal(t, mx);
	}
	inline friend bool operator < (const Surreal &x, const Surreal &y) {
		int mx = max(x.d, y.d);
		return (x.n << (mx - x.d)) < (y.n << (mx - y.d));
	}
	inline friend bool operator > (const Surreal &x, const Surreal &y) {
		return y < x;
	}
	inline friend bool operator <= (const Surreal &x, const Surreal &y) {
		return !(y < x);
	}
	inline friend bool operator >= (const Surreal &x, const Surreal &y) {
		return !(y > x);
	}
	inline friend Surreal operator - (const Surreal &x) {
		return Surreal(-x.n, x.d);
	}
	inline friend Surreal operator | (Surreal x, Surreal y) {
		assert(x < y);
		if (x < 0 && 0 < y) return 0;
		if (y <= 0) return -(-y | -x);
		Surreal v((x.n >> x.d) + 1);
		if (v < y) return v;
		int d = max(x.d, y.d);
		x.n <<= d - x.d;
		y.n <<= d - y.d;
		if (x.n + 1 == y.n) return Surreal(2 * x.n + 1, d + 1);
		while ((x.n >> 1) + 1 < ((y.n + 1) >> 1)) {
			x.n >>= 1, y.n = (y.n + 1) >> 1;
			d--;
		} assert(x.n + 1 == y.n - 1);
		return Surreal(x.n + 1, d);
	}
};
map <string, Surreal> mp;
Surreal calc(string st) {
	if (mp.count(st)) return mp[st];
	Surreal mx(-1e9), mn(1e9);
	F(i, 1, n) {
		if (st[i - 1] == '.' && st[i] == 'W') {
			string stt = st;
			swap(stt[i - 1], stt[i]);
			chkmax(mx, calc(stt));
		}
		if (st[i - 1] == '.' && st[i] == 'B') {
			string stt = st;
			swap(stt[i - 1], stt[i]);
			chkmin(mn, calc(stt));
		}
		if (st[i] == 'B') {
			string stt = st;
			stt[i] = '.';
			chkmax(mx, calc(stt));
		}
		if (st[i] == 'W') {
			string stt = st;
			stt[i] = '.';
			chkmin(mn, calc(stt));
		}
	}
	// cout << st << " " << mx.n << " " << mx.d << " " << mn.n << " " << mn.d << " " << (mx | mn).n << " " << (mx | mn).d << endl;
	return mp[st] = mx | mn;
}
signed main() {
	read(n);
	F(i, 1, n) {
		string t; cin >> t;
		F(j, 0, SZ(t)) st[j + 1] += t[j];
	}
	Surreal sum;
	F(i, 1, n) sum = sum + calc(' ' + st[i]);
	// cout << sum.n << ' ' << sum.d << endl;
	puts(sum > 0 ? "Takahashi" : "Snuke");
	return 0;
}

Submission Info

Judge Result