uva 10561 Treblecross(博弈)

#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
#include<iostream>  
using namespace std ;  
  
int sg[222] ;  
int g ( int k ) {  
    if ( sg[k] != -1 ) return sg[k] ;  
    int t = 0 ;  
    int i , j ;  
    int vis[222] ;  
    memset ( vis , 0 , sizeof ( vis ) ) ;  
    vis[g(k-3)] = vis[g(k-4)] = 1 ;  
    if ( k >= 5 ) vis[g(k-5)] = 1 ;  
    for ( i = 1 ; i + 5 <= k ; i ++ ) {  
        vis[g(i)^g(k-i-5)] = 1 ;  
    }  
    for ( i = 0 ; i < 222 ; i ++ )  
        if ( !vis[i] )  
             break ;  
    sg[k] = i ;  
    return sg[k] ;  
}  
  
int judge ( char *s ) {  
    int vis[222] ;  
    memset ( vis , 0 , sizeof ( vis ) ) ;  
    int i ;  
    int len = strlen ( s ) ;  
    for ( i = 0 ; i < len ; i ++ ) {  
        if ( s[i] == 'X' ) {  
            vis[i] = 1 ;  
            if ( i ) vis[i-1] = 1 ;  
            if ( i > 1 ) vis[i-2] = 1 ;  
            if ( i < len - 1 ) vis[i+1] = 1 ;  
            if ( i < len - 2 ) vis[i+2] = 1 ;  
        }  
    }  
    int ans = 0 ;  
    int last = 0 ;  
    i = 0 ;  
    while ( i < len ) {  
        while ( i < len && !vis[i] ) i ++ ;  
        if ( i > last ) ans ^= g ( i - last ) ;  
        while ( i < len && vis[i] ) i ++ ;  
        last = i ;  
    }  
    return ( ans != 0 ) ;  
}  
  
int st[11111] ;  
char s[222] ;  
  
int main () {  
    int cas , i , j , k ;  
    scanf ( "%d" , &cas ) ;  
    memset ( sg , -1 , sizeof ( sg ) ) ;  
    sg[0] = 0 ;  
    sg[1] = sg[2] = sg[3] = 1 ;  
    while ( cas -- ) {  
        int top = 0 ;  
        scanf ( "%s" , s ) ;  
        int len = strlen ( s ) ;  
        for ( i = 0 ; i < len - 1 ; i ++ ) {  
            if ( s[i] == 'X' ) {  
                if ( s[i+1] == 'X' ) {  
                    if ( i ) st[++top] = i - 1 ;  
                    if ( i + 2 < len ) st[++top] = i + 2 ;  
                }  
                if ( i + 2 < len && s[i+2] == 'X' ) {  
                    st[++top] = i + 1 ;  
                }  
            }  
        }  
        sort ( st + 1 , st + top + 1 ) ;  
        top = unique ( st + 1 , st + top + 1 ) - st - 1 ;  
        if ( top ) {  
            puts ( "WINNING" ) ;  
            for ( i = 1 ; i <= top ; i ++ ){  
                if ( i != 1 ) printf ( " " ) ;  
                printf ( "%d" , st[i] + 1 ) ;  
            }  
            puts ( "" ) ;  
            continue ;  
        };  
        int flag = 0 ;  
        int vis[222] ;  
        memset ( vis , 0 , sizeof ( vis ) ) ;  
        for ( i = 0 ; i < len ; i ++ ) {  
            if ( s[i] == 'X' ) {  
                vis[i] = 1 ;  
                if ( i ) vis[i-1] = 1 ;  
                if ( i > 1 ) vis[i-2] = 1 ;  
                if ( i < len - 1 ) vis[i+1] = 1 ;  
                if ( i < len - 2 ) vis[i+2] = 1 ;  
            }  
        }  
        top = 0 ;  
        for ( i = 0 ; i < len ; i ++ ) {  
            if ( !vis[i] ) {  
                s[i] = 'X' ;  
                int k = judge ( s ) ;  
                s[i] = '.' ;  
                if ( !k ) st[++top] = i ;  
            }  
        }  
        if ( !top ) printf ( "LOSING\n\n" ) ;  
        else {  
            printf ( "WINNING\n" ) ;  
            for ( i = 1 ; i <= top ; i ++ ) {  
                if ( i != 1 ) printf ( " " ) ;  
                printf ( "%d" , st[i] + 1 ) ;  
            }  
            puts ( "" ) ;  
        }  
    }  
    return 0 ;  
}