Участник:Morgachev/REMGAME

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/REMGAME/

C++14 (clang8.0)


#include <cstdio>
 
int T;
int M;
int move[250];
char memo[1 << 25];
 
char solve(int mask) {
    if (mask == 0)
        return 1;
 
    if (memo[mask])
        return memo[mask];
 
    for (int i = 0; i < M; i++) {
        if ((mask & move[i]) == move[i] && solve(mask ^ move[i]) == 2) {
            memo[mask] = 1;
            return memo[mask];
        }
    }
    memo[mask] = 2;
    return memo[mask];
}
 
int main() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            for (int k = i, mv = 0; k < 5; k++) {
                mv |= 1 << (k * 5 + j);
                move[M++] = mv;
            }
            for (int k = j, mv = 0; k < 5; k++) {
                mv |= 1 << (i * 5 + k);
                move[M++] = mv;
            }
        }
    }
 
    scanf("%d", &T);
    while (T--) {
 
        int board = 0;
        for (int i = 0; i < 25; i++) {
            int x;
            scanf("%d", &x);
            if (x)
                board |= (1 << i);
        }
 
        if (solve(board) == 1)
            printf("winning\n");
        else
            printf("losing\n");
    }
 
    return 0;
}