QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#414949#4234. Tic Tac Toe Countingivan_len#TL 0ms3520kbC++202.5kb2024-05-20 04:49:062024-05-20 04:49:06

Judging History

This is the latest submission verdict.

  • [2024-05-20 04:49:06]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 3520kb
  • [2024-05-20 04:49:06]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define PB push_back
#define MP make_pair
#define A first
#define B second
#define SZ(x) int(x.size())
#define FR(i, a, b) for (int i = (a); i < (b); ++i)
#define FOR(i, n) FR(i, 0, n)
const int M = 1000000007;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n;

int State(vector<vector<int>>& s) {
    int win = 0;
    FOR(i, 3) {
        if (s[i][0] == s[i][1] && s[i][0] == s[i][2]) {
            if (s[i][0] == 1) win |= 1;
            if (s[i][0] == 2) win |= 2;
        }
        if (s[0][i] == s[1][i] && s[0][i] == s[2][i]) {
            if (s[0][i] == 1) win |= 1;
            if (s[0][i] == 2) win |= 2;
        }
    }
    if (s[0][0] == s[1][1] && s[0][0] == s[2][2]) {
        if (s[0][0] == 1) win |= 1;
        if (s[0][0] == 2) win |= 2;
    }
    if (s[2][0] == s[1][1] && s[2][0] == s[0][2]) {
        if (s[1][1] == 1) win |= 1;
        if (s[1][1] == 2) win |= 2;
    }
    return win;
}

int X, O;

void dfs(vector<vector<int>>& state) {
    int win = State(state);
    if (win == 3) return;
    if (win == 1) {
        X++;
        return;
    }
    if (win == 2) {
        O++;
        return;
    }
    int cnt = 0;
    FOR(i, 3) {
        FOR(j, 3) {
            if (state[i][j] != 0) cnt++;
        }
    }
    if (cnt == 9) return;
    int c = ((cnt & 1)?2:1);
    FOR(i, 3) {
        FOR(j, 3) {
            if (state[i][j] == 0) {
                vector<vector<int>> nxt = state;
                nxt[i][j] = c;
                dfs(nxt);
            }
        }
    }
}

// X for 1, O for 2; . for 0
void solve() {
    vector<vector<int>> state(3, vector<int>(3));
    string s;
    cin >> s;
// cerr << s << '\n';
    X = 0; O = 0;
    FOR(i, 3) {
        FOR(j, 3) {
            if (s[i * 3 + j] == 'X') state[i][j] = 1;
            if (s[i * 3 + j] == 'O') state[i][j] = 2;
        }
    }
    int Xcnt = 0, Ocnt = 0;
    FOR(i, 3) {
        FOR(j, 3) {
            if (state[i][j] == 1) Xcnt++;
            if (state[i][j] == 2) Ocnt++;
        }
    }
// cerr << Xcnt << ' ' << Ocnt << '\n';    
    if (Xcnt < Ocnt || Xcnt > Ocnt + 1) {
        cout << "-1 -1\n";
        return;
    }
    if (State(state) == 3) {
        cout << "-1 -1\n";
        return;
    }

    dfs(state);
    cout << X << ' ' << O << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int numtests;
    cin >> numtests;
    while(numtests--) {
        solve();
    }
}


详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3520kb

input:

4
XX..O....
X...OX...
OOOX.X.X.
OOOXXX...

output:

191 194
232 200
0 1
-1 -1

result:

ok 4 lines

Test #2:

score: -100
Time Limit Exceeded

input:

100000
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
......

output:


result: