UVa 10561 - Treblecross

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>



#define ll long long

#define lint long long

using namespace std;



const int N=205;

int sg[N];

int dp(int x)

{

    if(sg[x]!=-1)

    return sg[x];

    if(x==0)

    return (sg[x]=0);

    bool ok[N];

    memset(ok,false,sizeof(ok));

    for(int i=1;i<=x;++i)

    {

        int k=(dp(max(0,i-3))^dp(max(0,x-i-2)));

        ok[k]=true;

    }

    for(int i=0;i<N;++i)

    if(!ok[i])

    {sg[x]=i;break;}

    return sg[x];

}

bool ok(string s)

{

    for(unsigned int i=0;i<s.size()-2;++i)

    {

        if(s[i]=='X'&&s[i+1]=='X'&&s[i+2]=='X')

        return true;

    }

    return false;

}

bool ok1(string s)

{

    for(unsigned int i=0;i<s.size();++i)

    if(s[i]=='.')

    {

        s[i]='X';

        if(ok(s))

        return false;

        s[i]='.';

    }

    int nim=0;

    int tmp=0;

    for(unsigned int i=0;i<s.size();++i)

    {

        if(s[i]=='X'||(i>=1&&s[i-1]=='X')||(i>=2&&s[i-2]=='X')||(i+1<s.size()&&s[i+1]=='X')||(i+2<s.size()&&s[i+2]=='X'))

        {nim=(nim^dp(tmp));tmp=0;}

        else

        ++tmp;

    }

    nim=(nim^dp(tmp));

    if(nim==0) return true;

    return false;

}

void solve(vector<int> &vt,string &s)

{

    for(unsigned int i=0;i<s.size();++i)

    if(s[i]=='.')

    {

        s[i]='X';

        if(ok(s)||ok1(s))

        vt.push_back(i+1);

        s[i]='.';

    }

}

int main()

{

    //freopen("data.in","r",stdin);

    memset(sg,-1,sizeof(sg));

    int T;

    cin>>T;

    while(T--)

    {

        string s;

        cin>>s;

        vector<int>vt;

        solve(vt,s);

        if(vt.size()==0)

        cout<<"LOSING"<<endl;

        else

        cout<<"WINNING"<<endl;

        for(unsigned int i=0;i<vt.size();++i)

        {

            if(i>0) cout<<" ";

            cout<<vt[i];

        }

        cout<<endl;

    }

    return 0;

}