/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 324.0 KiB
#2 Accepted 2ms 320.0 KiB
#3 Accepted 2ms 532.0 KiB
#4 Accepted 2ms 320.0 KiB
#5 Accepted 1ms 336.0 KiB
#6 Accepted 1ms 324.0 KiB
#7 Accepted 2ms 504.0 KiB
#8 Accepted 1ms 532.0 KiB
#9 Accepted 1ms 536.0 KiB
#10 Accepted 1ms 532.0 KiB
#11 Accepted 2ms 320.0 KiB
#12 Accepted 2ms 324.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int sz = 2e5 + 100;
const ll mod = 1e9 + 7;

int t, cs;
string board[3];
vector <int> valid;
int dp[1 << 9];

int m(int x) {
    return 1 << x;
}

int check(int mask) {
    if (~dp[mask]) return dp[mask];
    dp[mask] = 0;
    for (const int& validMask: valid) {
        if ((mask & validMask) == validMask) {
            return dp[mask] = 1;
        }
    }
    for (int i = 0; i < 9; i++) {
        if (mask & m(i)) continue;
        dp[mask] |= !check(mask | m(i));
    }
    return dp[mask];
}

int main() {

    valid.push_back(m(0) | m(1) | m(2));
    valid.push_back(m(3) | m(4) | m(5));
    valid.push_back(m(6) | m(7) | m(8));

    valid.push_back(m(0) | m(3) | m(6));
    valid.push_back(m(1) | m(4) | m(7));
    valid.push_back(m(2) | m(5) | m(8));

    valid.push_back(m(0) | m(4) | m(8));
    valid.push_back(m(6) | m(4) | m(2));

    memset(dp, -1, sizeof dp);

    check(0);

    while (cin >> t) {

        while (t--) {

            int mask = 0;

            for (int i = 0; i < 3; i++) {
                cin >> board[i];
                for (const char &c: board[i]) {
                    mask <<= 1;
                    mask |= (c == 'X');
                }
            }

            cout << "Game #" << ++cs << ": " << (!dp[mask] ? "Bob" : "Alice") << "\n";

        }

    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1089 Game of Tic Tac Toe
Language
C++17 (G++ 13.2.0)
Submit At
2024-10-20 20:42:32
Judged At
2024-11-11 02:36:30
Judged By
Score
100
Total Time
2ms
Peak Memory
536.0 KiB