SRM534-D1-250 EllysCheckers

#define ll long long
#include <bits/stdc++.h>
using namespace std;

/*
Ordered set usage:
order_of_key (k) : Number of items strictly smaller than k.
find_by_order(k) : K-th element in a set (counting from zero).
*/

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int OO = 1e9;
const double EPS = 1e-9;
int mem[2000000];
class EllysCheckers
{
public:

    int solve(int state, int rem)
    {
        //cout << "here at state = " << state << " rem = " << rem << "\n";
        if(rem == 0) {
            return 0;
        }
        if(mem[state] != -1) {
            return mem[state];
        }
        bool ret = 0;
        for(int i = 19; i >= 1; i--) {
            int pos = (1 << i);
            if(state&pos) {
                if(!(state&(pos/2))) {
                    if(i == 1) {
                        ret = max(ret,!solve(state^pos,rem-1));
                    }
                    else {
                        ret = max(ret,!solve((state^pos) | (pos/2),rem));
                    }
                }
                else if(i >= 3 && (state&(pos/4)) && !(state&(pos/8))) {
                    if(i == 3) {
                        ret = max(ret,!solve(state^pos,rem-1));
                    }
                    else {
                        ret = max(ret,!solve((state^pos) | (pos/8),rem));
                    }
                }
            }
        }
        mem[state] = ret;
        return ret;
    }

    string getWinner(string board)
    {
        int state = 0;
        int pos = 2;
        int cnt = 0;
        for(int i = board.size()-2; i >= 0; i--)
        {
            if(board[i] == 'o')
            {
                state |= pos;
                cnt++;
            }
            pos <<= 1;
        }
        for(int i = 0; i <= state; i++) {
            mem[i] = -1;
        }
        return (solve(state, cnt) ? "YES":"NO");
    }
};