EllysCheckers.cpp

#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pi pair<int,int>
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define ln(x) ((int)x.length())
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define dbg(x) cout << #x << ": " << x << endl
#define clr(x,v) memset(x, v, sizeof(x))
#define dblout(x) cout << setprecision(x) << fixed;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const double eps = 1e-9;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
const int MAXN = 1e6 + 5;

class EllysCheckers
{
public:
    string getWinner(string);
};

#define M 20
int dp[1 << M];
bool solve(bitset<M> mask)
{
    if(!mask.to_ulong())
        return 0;

    int &ret = dp[mask.to_ulong()];
    if(~ret)
        return ret;

    bool win = false;
    for(int i = 0; i < M; i++)
    {
        if(mask[i])
        {
            if(i - 1 >= 0 && !mask[i - 1])
            {
                // try step
                bitset<M> nmask = mask;
                nmask[i] = 0;
                nmask[i - 1] = 1;
                nmask[0] = 0;
                win |= solve(nmask) ^ 1;
            }

            if(i - 3 >= 0 && mask[i - 1] && mask[i - 2] && !mask[i - 3])
            {
                // try jump
                bitset<M> nmask = mask;
                nmask[i] = 0;
                nmask[i - 3] = 1;
                nmask[0] = 0;
                win |= solve(nmask) ^ 1;
            }
        }
    }

    return (ret = win);
}

string EllysCheckers::getWinner(string board)
{
    bitset<M> mask(0);
    int n = ln(board);
    for(int i = n - 1; i >= 0; i--)
        mask[n - i - 1] = (board[i] == 'o');
    mask[0] = 0;
    clr(dp, -1);
    bool win = solve(mask);
    if(win)
        return "YES";
    else
        return "NO";
}
// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.4 (beta) modified by pivanof
bool KawigiEdit_RunTest(int testNum, string p0, bool hasAnswer, string p1) {
	cout << "Test " << testNum << ": [" << "\"" << p0 << "\"";
	cout << "]" << endl;
	EllysCheckers *obj;
	string answer;
	obj = new EllysCheckers();
	clock_t startTime = clock();
	answer = obj->getWinner(p0);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << "\"" << p1 << "\"" << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << "\"" << answer << "\"" << endl;
	if (hasAnswer) {
		res = answer == p1;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	string p0;
	string p1;
	
	{
	// ----- test 0 -----
	p0 = ".o...";
	p1 = "YES";
	all_right = KawigiEdit_RunTest(0, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	p0 = "..o..o";
	p1 = "YES";
	all_right = KawigiEdit_RunTest(1, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	p0 = ".o...ooo..oo..";
	p1 = "NO";
	all_right = KawigiEdit_RunTest(2, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	p0 = "......o.ooo.o......";
	p1 = "YES";
	all_right = KawigiEdit_RunTest(3, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	p0 = ".o..o...o....o.....o";
	p1 = "NO";
	all_right = KawigiEdit_RunTest(4, p0, true, p1) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// END KAWIGIEDIT TESTING


//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!