QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#416675#4234. Tic Tac Toe Countingfrizzfrizz#WA 39ms4768kbC++143.6kb2024-05-22 02:17:332024-05-22 02:17:33

Judging History

This is the latest submission verdict.

  • [2024-05-22 02:17:33]
  • Judged
  • Verdict: WA
  • Time: 39ms
  • Memory: 4768kb
  • [2024-05-22 02:17:33]
  • Submitted

answer

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

#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)

int T;
vector<vector<int> > regs;
unordered_map<string, int> dist, xWin, oWin;
vector<string> ofDist[10];
int status(string b) // assuming a valid board, is it 0 not over, 1 win for X, 2 win for O, 3 tie
{
    FOR(ri, SZ(regs))
    {
        FOR(i, 2)
        {
            if (b[regs[ri][i]] != b[regs[ri][i + 1]])
                break;
            if (i == 1 && b[regs[ri][i]] == 'X')
                return 1;
            if (i == 1 && b[regs[ri][i]] == 'O')
                return 2;
        }
    }
    FOR(i, 3)
        FOR(j, 3)
            if (b[3 * i + j] == '.')
                return 0;
    return 3;
}

vector<string> get_neis(string b) // assuming correct board state, generate next states
{
    int stat = status(b), xCo = 0, oCo = 0;
    if (stat != 0)
        return {};
    vector<int> dotLoc;
    vector<string> neis;
    FOR(i, 9)
    {
        if (b[i] == 'X')
            xCo++;
        if (b[i] == 'O')
            oCo++;
        if (b[i] == '.')
            dotLoc.push_back(i);
    }
    if (oCo == xCo)
    {
        FOR(i, SZ(dotLoc))
        {
            string nex = b;
            nex[dotLoc[i]] = 'X';
            neis.push_back(nex);
        }
        return neis;
    }
    FOR(i, SZ(dotLoc))
    {
        string nex = b;
        nex[dotLoc[i]] = 'O';
        neis.push_back(nex);
    }
    return neis;
}

int main()
{
    cin >> T;
    FOR(i, 3)
    {
        vector<int> v;
        FOR(j, 3)
            v.push_back(3 * i + j);
        regs.push_back(v);
    }
    FOR(j, 3)
    {
        vector<int> v;
        FOR(i, 3)
            v.push_back(3 * i + j);
        regs.push_back(v);
    }
    regs.push_back({0, 4, 8});
    regs.push_back({2, 4, 6});
    queue<string> q;
    string st = ".........";
    q.push(st);
    dist[st] = 0;
    while (!q.empty())
    {
        string cur = q.front();
        q.pop();
        vector<string> neis = get_neis(cur);
        FOR(i, SZ(neis))
        {
            if (dist.find(neis[i]) == dist.end())
            {
                dist[neis[i]] = dist[cur] + 1;
                ofDist[dist[neis[i]]].push_back(neis[i]);
                q.push(neis[i]);
            }
        }
    }
    for (int d = 9; d >= 0; d--)
    {
        FOR(i, SZ(ofDist[d]))
        {
            int stat = status(ofDist[d][i]);
            if (stat == 1)
            {
                xWin[ofDist[d][i]] = 1;
                oWin[ofDist[d][i]] = 0;
                continue;
            }
            if (stat == 2)
            {
                xWin[ofDist[d][i]] = 0;
                oWin[ofDist[d][i]] = 1;
                continue;
            }
            if (stat == 3)
            {
                xWin[ofDist[d][i]] = 0;
                oWin[ofDist[d][i]] = 0;
                continue;
            }
            vector<string> neis = get_neis(ofDist[d][i]);
            xWin[ofDist[d][i]] = 0;
            oWin[ofDist[d][i]] = 0;
            FOR(j, SZ(neis))
            {
                xWin[ofDist[d][i]] += xWin[neis[j]];
                oWin[ofDist[d][i]] += oWin[neis[j]];
            }
        }
    }
    while (T--)
    {
        string s;
        cin >> s;
        if (xWin.find(s) == xWin.end())
            cout << "-1 -1\n";
        else
            cout << xWin[s] << " " << oWin[s] << "\n";
    }
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 4768kb

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
Wrong Answer
time: 39ms
memory: 4716kb

input:

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

output:

-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
...

result:

wrong answer 1st lines differ - expected: '131184 77904', found: '-1 -1'