QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#416675 | #4234. Tic Tac Toe Counting | frizzfrizz# | WA | 39ms | 4768kb | C++14 | 3.6kb | 2024-05-22 02:17:33 | 2024-05-22 02:17:33 |
Judging History
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";
}
}
Details
Tip: Click on the bar to expand more detailed information
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'