p289.ans1
======================
X wins.
0 wins.
Game is a draw.
Illegal position.
X wins.

=================
p289.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int STATES = 19683;
const int lines[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {0, 3, 6},
                         {1, 4, 7}, {2, 5, 8}, {0, 4, 8}, {2, 4, 6}};

int dp[STATES];
bool reachable[STATES];

int get_cell(int state, int i) {
    for(int j = 0; j < i; j++) {
        state /= 3;
    }
    return state % 3;
}

int set_cell(int state, int i, int v) {
    int pw = 1;
    for(int j = 0; j < i; j++) {
        pw *= 3;
    }
    return state + v * pw;
}

int check_winner(int state) {
    for(auto& line: lines) {
        int a = get_cell(state, line[0]);
        int b = get_cell(state, line[1]);
        int c = get_cell(state, line[2]);
        if(a && a == b && b == c) {
            return a;
        }
    }
    return 0;
}

int count_pieces(int state) {
    int cnt = 0;
    for(int i = 0; i < 9; i++) {
        if(get_cell(state, i)) {
            cnt++;
        }
    }
    return cnt;
}

void precompute() {
    memset(reachable, false, sizeof(reachable));
    reachable[0] = true;

    function<void(int)> dfs = [&](int state) {
        int w = check_winner(state);
        if(w) {
            dp[state] = (w == 1) ? 1 : -1;
            return;
        }
        int cnt = count_pieces(state);
        if(cnt == 9) {
            dp[state] = 0;
            return;
        }
        int player = (cnt % 2 == 0) ? 1 : 2;
        bool maximizing = (player == 1);
        dp[state] = maximizing ? -2 : 2;
        for(int i = 0; i < 9; i++) {
            if(get_cell(state, i) == 0) {
                int nxt = set_cell(state, i, player);
                if(!reachable[nxt]) {
                    reachable[nxt] = true;
                    dfs(nxt);
                }
                if(maximizing) {
                    dp[state] = max(dp[state], dp[nxt]);
                } else {
                    dp[state] = min(dp[state], dp[nxt]);
                }
            }
        }
    };

    dfs(0);
}

string board[3];

void solve() {
    // We can do a DP over all 3^9 possible board states by doing a DFS from
    // the empty board. Each state encodes the board in base 3 (0 = empty, 1 =
    // X, 2 = O). For each state we compute the minimax outcome with perfect
    // play: 1 = X wins, -1 = O wins, 0 = draw. Only states reachable through
    // valid play are marked, so illegal positions are detected by checking
    // reachability. Each query then just encodes the board and looks up the
    // precomputed result. In practice only ~5k states out of 19683 are
    // reachable through valid play.

    int state = 0;
    for(int i = 0; i < 9; i++) {
        char c = board[i / 3][i % 3];
        if(c == 'X') {
            state = set_cell(state, i, 1);
        } else if(c == '0') {
            state = set_cell(state, i, 2);
        }
    }

    if(!reachable[state]) {
        cout << "Illegal position.\n";
    } else if(dp[state] == 1) {
        cout << "X wins.\n";
    } else if(dp[state] == -1) {
        cout << "0 wins.\n";
    } else {
        cout << "Game is a draw.\n";
    }
}

bool read() {
    cin >> board[0];
    if(board[0] == "Qc") {
        return false;
    }
    cin >> board[1] >> board[2];
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    precompute();

    while(read()) {
        solve();
    }

    return 0;
}

=================
p289.in1
======================
..X
.X0
...

..X
.0.
XX0

X0X
X0.
0X.

X0X
X0X
X0X

X0X
0X0
X0X

Qc

=================
statement.txt
======================
289. Challenging Tic-Tac-Toe
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Qc and He play the famous game of Tic-Tac-Toe. The game is played on a 3x3 board. Qc plays with X-s, He plays with 0-s. The players make moves in turn, Qc moves first. The object of the game is to get three of your marks in a row. If there is no empty square to put the mark to, the game ends in a draw.
Given the position in a game and assuming that both Qc and He play perfectly, you have to detect who would win the game, or that the game would end in a draw. If the position given is illegal, that is, it cannot occur in the game, you must report so.

Input
The input file contains one or more test cases. Each test case consists of four lines. Each of the first three lines contains three characters, these lines describe the position on the board. The fourth line of each test case is empty.
The position on the board is specified using characters "X", "0" (zero), and "." (dot). The input file is terminated by the string containing the word "Qc" on a line by itself. You may assume that no position occurs in the input file more than once.

Output
Print one statement for each test case. Refer to the sample output for exact statements.

Sample test(s)

Input
..X
.X0
...

..X
.0.
XX0

X0X
X0.
0X.

X0X
X0X
X0X

X0X
0X0
X0X

Qc

Output
X wins.
0 wins.
Game is a draw.
Illegal position.
X wins.

=================
