QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#105448 | #4234. Tic Tac Toe Counting | marsxiang5902 | WA | 22ms | 4232kb | C++17 | 1.6kb | 2023-05-14 04:37:49 | 2023-05-14 04:37:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MN = 9, MD = 1<<MN*2;
int T, dp[MD][2];
inline int bitAt(int b, int i) { return (b>>i*2)&3; }
inline bool invalid(int b) {
for (int i = 0; i < 9; i++)
if (bitAt(b, i) == 3) return 1;
return 0;
}
inline int isWin(int b) {
int ans = 0;
for (int z: {1,2}) {
bool b3 = 1, b4 = 1;
for (int i = 0; i < 3; i++) {
bool b1 = 1, b2 = 1;
for (int j = 0; j < 3; j++) {
b1 &= bitAt(b, i*3+j) == z;
b2 &= bitAt(b, j*3+i) == z;
}
if (b1 || b2) ans |= z;
b3 &= bitAt(b, i*3+i) == z;
b4 &= bitAt(b, i*3+2-i) == z;
}
if (b3 || b4) ans |= z;;
} return ans;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
for (int b = MD; b--; ) {
if (invalid(b)) continue;
if (int w = isWin(b); w) {
if (w < 3) dp[b][w-1] = 1;
continue;
}
for (int i = 0; i < 9; i++) {
int turn = __builtin_popcount(b) & 1 ? 2 : 1;
if (bitAt(b, i) == 0) {
dp[b][0] += dp[b|turn<<i*2][0];
dp[b][1] += dp[b|turn<<i*2][1];
}
}
}
cin >> T;
for (int t = 0; t < T; t++) {
int b = 0; string s; cin >> s;
for (int i = 0; i < 9; i++)
b |= (s[i] == 'O' ? 2 : s[i] == 'X') << i*2;
if (!dp[b][0] && !dp[b][1]) printf("-1 -1\n");
else printf("%d %d\n", dp[b][0], dp[b][1]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 4232kb
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: 14ms
memory: 4208kb
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: 22ms
memory: 4212kb
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'