SRM522-D1-250 RowAndCoins

#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;

class RowAndCoins
{
public:
    string s;
    int mem[1000000][2];
    int p[20];

    int solve(int state, int turn, int emp)
    {

        if(mem[state][turn] != -1)
        {
            return mem[state][turn];
        }

        if(emp == 1)
        {
            for(int i = 0; i < s.size(); i++)
            {
                if(!(state&p[i]))
                {
                    return s[i] == 'B';
                }
            }
        }
        int &ret = mem[state][turn];
        ret = !turn;
        for(int i = 0; i < s.size(); i++) {
            if(!(state&p[i])) {
                int new_state = state | p[i];
                for(int j = i; j < s.size(); j++) {
                    if(!(state&p[j]) && j-i+1 < emp) {
                        new_state |= p[j];
                        int curr = solve(new_state,!turn,emp-(j-i+1));
                        if(curr == turn) {
                            ret = turn;
                            return ret;
                        }
                    }
                    else {
                        break;
                    }
                }
            }
        }
        return ret;
    }

    string getWinner(string cells)
    {
        s = cells;
        int x = (1 << (cells.size()+1));
        for(int i = 0; i < 20; i++) {
            p[i] = (1 << i);
        }
        for(int i = 0; i <= x; i++)
        {
            mem[i][0] = mem[i][1] = -1;
        }
        return (solve(0,0,cells.size()) ? "Bob":"Alice");
    }
};

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    return 0;
}