QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#72793 | #4234. Tic Tac Toe Counting | Linshey# | WA | 25ms | 4376kb | C++23 | 1.8kb | 2023-01-19 13:27:12 | 2023-01-19 13:27:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int f[1 << 18], g[1 << 18];
int mp[3][3], cov = 0;
inline void cons(int S)
{
cov = 0;
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (mp[i][j] = (S >> (i * 3 + j << 1) & 3)) cov ^= 1;
}
inline int Cons()
{
int S = 0;
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) S |= mp[i][j] << (i * 3 + j << 1);
return S;
}
inline bool ck(int x)
{
for (int i = 0; i < 3; i++)
{
bool is = 1;
for (int j = 0; j < 3; j++) if (mp[i][j] != x) { is = 0; break; }
if (is) return true;
}
for (int i = 0; i < 3; i++)
{
bool is = 1;
for (int j = 0; j < 3; j++) if (mp[j][i] != x) { is = 0; break; }
if (is) return true;
}
return (mp[0][0] == x && mp[1][1] == x && mp[2][2] == x) || (mp[2][0] == x && mp[1][1] == x && mp[0][2] == x);
}
int main()
{
for (int S = (1 << 18) - 1; S >= 0; S--)
{
bool is = 0;
for (int i = 0; i < 9; i++) if ((S >> (i << 1) & 3) == 3) { is = 1; break; }
if (is) continue;
cons(S);
bool f1 = ck(1), f2 = ck(2);
if (f1 && f2) continue;
if (f1) { f[S] = 1; continue; }
if (f2) { g[S] = 1; continue; }
int t = cov + 1;
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (!mp[i][j])
{
mp[i][j] = t;
int T = Cons();
f[S] += f[T], g[S] += g[T];
mp[i][j] = 0;
}
}
int Q; scanf("%d", &Q); while (Q--)
{
char s[11];
scanf("%s", s);
int S = 0;
for (int i = 0; i < 9; i++) S |= (int(s[i] != '.') + int(s[i] == 'O')) << (i << 1);
if (f[S] == 0 && g[S] == 0) puts("-1 -1");
else printf("%d %d\n", f[S], g[S]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 4372kb
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: 0
Accepted
time: 13ms
memory: 4212kb
input:
100000 ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......
output:
131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 1...
result:
ok 100000 lines
Test #3:
score: -100
Wrong Answer
time: 25ms
memory: 4376kb
input:
100000 ......... X........ O........ .X....... XX....... OX....... .O....... XO....... OO....... ..X...... X.X...... O.X...... .XX...... XXX...... OXX...... .OX...... XOX...... OOX...... ..O...... X.O...... O.O...... .XO...... XXO...... OXO...... .OO...... XOO...... OOO...... ...X..... X..X..... O.....
output:
131184 77904 14652 7896 3384 16044 14232 10176 1861 144 1798 1276 5904 16392 2048 756 624 1878 14652 7896 1751 0 1832 1132 1861 144 1 0 220 248 2048 756 268 144 136 316 3384 16044 1832 1132 120 1966 1798 1276 220 248 16 348 624 1878 136 316 0 1 14232 10176 1861 144 1798 1276 2728 288 286 36 264 188 ...
result:
wrong answer 3rd lines differ - expected: '-1 -1', found: '3384 16044'