Решение задачи "Игра в зачеркивание" с Меньшиков

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <list>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int WIN = 1;      // ход выигрышный
const int FAIL = 2;     // ход проигрышный
const int NAN = 0;      // нельзя сделать ход
int n,len;
string str;
long long curState;
long long mask;
long long one = 1;
 
map<long long, vector<long long> > adj;
vector<long long> mas;
vector<int> win;
void input()
{
    cin>>n>>len;
    cin>>str;
    int pos = 0;
    for (int i = str.size()-1;i>=0;i--)
    {
        if (str[i] == 'X')
            curState |= one<<pos;
        pos++;
    }
}
void GenMask()
{
    // len == 2 mask = ..0011000...
    int hPos = n - 1; // позиция старшего единичного бита
    for (int i = 0; i < len && hPos - i >=0;i++)
        mask |= one << (hPos - i);
}
void GenAdj(long long state)
{
    if (adj.find(state) != adj.end())
        return;
    mas.push_back(state);
    long long curMask = mask;
    for (int i = 0; i <= n - len; i++)
    {
        if ((state & curMask) == 0)
        {
            long long next = state | curMask;
            adj[state].push_back(next);
            GenAdj(next);
        }
        curMask >>= 1;
    }       
}
void FindAnswer()
{
    sort(mas.begin(), mas.end());
    mas.resize(unique(mas.begin(),mas.end()) - mas.begin());
    win = vector<int>(mas.size(),0);
 
    for (int i = mas.size()-1; i >= 0; i--)
    {
        if (adj.find(mas[i]) == adj.end())
            win[i] = FAIL;
        else if (adj[mas[i]].size() == 1)
            win[i] = WIN;
        else
        {
            vector<long long> &v = adj[mas[i]];
            bool isCurWin = false;
            for (int j = 0; j< v.size();j++)
            {
                int pos = lower_bound(mas.begin(), mas.end(), v[j]) - mas.begin();
                if (win[pos] == FAIL)
                {
                    isCurWin = true;
                    break;
                }
            }
            win[i] = isCurWin ? WIN : FAIL;
        }
    }
}
void solve()
{
    GenMask();
    GenAdj(curState);
    FindAnswer();
}
void output()
{
    if (adj.empty())
        cout<<NAN;
    else
        cout<<win[0];
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    output();
 
    return 0;
}