QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253736#4234. Tic Tac Toe Countingchen_zexingAC ✓26ms3868kbC++172.2kb2023-11-17 13:26:202023-11-17 13:26:20

Judging History

This is the latest submission verdict.

  • [2023-11-17 13:26:20]
  • Judged
  • Verdict: AC
  • Time: 26ms
  • Memory: 3868kb
  • [2023-11-17 13:26:20]
  • Submitted

answer

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int dp[20005][3];
void solve(char c[3][3],int v,int type){
    if(dp[v][1]!=-1) return;
    /*
    cout<<v<<endl;
    for(int i=0;i<3;i++,puts(""))
        for(int j=0;j<3;j++)
            cout<<c[i][j]<<" ";
            */
    for(int i=0;i<3;i++){
        int ff=1;
        for(int j=0;j<3;j++) if(c[i][j]!=c[i][0]||c[i][j]=='.') ff=0;
        if(ff){
            if(c[i][0]=='X') dp[v][1]=1,dp[v][2]=0;
            else dp[v][1]=0,dp[v][2]=1;
            return;
        }
    }
    for(int i=0;i<3;i++){
        int ff=1;
        for(int j=0;j<3;j++) if(c[j][i]!=c[0][i]||c[j][i]=='.') ff=0;
        if(ff){
            if(c[0][i]=='X') dp[v][1]=1,dp[v][2]=0;
            else dp[v][1]=0,dp[v][2]=1;
            return;
        }
    }
    if(c[0][0]==c[1][1]&&c[1][1]==c[2][2]&&c[0][0]!='.'){
        if(c[0][0]=='X') dp[v][1]=1,dp[v][2]=0;
        else dp[v][1]=0,dp[v][2]=1;
        return;
    }
    if(c[2][0]==c[1][1]&&c[1][1]==c[0][2]&&c[2][0]!='.'){
        if(c[2][0]=='X') dp[v][1]=1,dp[v][2]=0;
        else dp[v][1]=0,dp[v][2]=1;
        return;
    }
    dp[v][1]=dp[v][2]=0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(c[i][j]=='.'){
                if(type==1) c[i][j]='X';
                else c[i][j]='O';
                solve(c,v+(pow(3,i*3+j)*type+1e-6),3-type);
                dp[v][1]+=dp[v+int(pow(3,i*3+j)*type+1e-6)][1],dp[v][2]+=dp[v+int(pow(3,i*3+j)*type+1e-6)][2];
                c[i][j]='.';
            }
}
int main() {
    int T = 1, kase = 0;
    //cin >> T;
    while (T--) {
        memset(dp,-1,sizeof(dp));
        char c[3][3];
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                c[i][j]='.';
        solve(c,0,1);
        int t;
        cin>>t;
        while(t--){
            char s[10];
            scanf("%s",s);
            int eq=0;
            for(int i=0;i<10;i++){
                if(s[i]=='X') eq+=pow(3,i);
                else if(s[i]=='O') eq+=pow(3,i)*2;
            }
            printf("%d %d\n",dp[eq][1],dp[eq][2]);
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3772kb

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: 3868kb

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: 0
Accepted
time: 17ms
memory: 3796kb

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
-1 -1
14232 10176
-1 -1
1798 1276
-1 -1
2048 756
-1 -1
14652 7896
-1 -1
1832 1132
-1 -1
-1 -1
220 248
2048 756
268 144
-1 -1
-1 -1
1832 1132
-1 -1
1798 1276
220 248
-1 -1
-1 -1
-1 -1
-1 -1
14232 10176
-1 -1
1798 1276
-1 -1
-1 -1
264 188
1868 1080
239 126
-1 -1
-1 -1
-1 -1
312...

result:

ok 100000 lines

Test #4:

score: 0
Accepted
time: 13ms
memory: 3864kb

input:

100000
.........
.........
.........
.........
.........
.........
........O
........O
........O
........O
........O
........X
........X
........X
........X
........X
.......O.
.......O.
.......O.
.......O.
.......O.
.......OO
.......OO
.......OO
.......OO
.......OO
.......OX
.......OX
.......OX
......

output:

131184 77904
131184 77904
131184 77904
131184 77904
131184 77904
131184 77904
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
14652 7896
14652 7896
14652 7896
14652 7896
14652 7896
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
2048 756
2048 756
2048 756
2048 756
2048 756
14232 10176
14232 10176
14232 10...

result:

ok 100000 lines

Test #5:

score: 0
Accepted
time: 17ms
memory: 3828kb

input:

100000
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXO
XXXXXXXXO
XXXXXXXXO
XXXXXXXXO
XXXXXXXXO
XXXXXXXX.
XXXXXXXX.
XXXXXXXX.
XXXXXXXX.
XXXXXXXX.
XXXXXXXOX
XXXXXXXOX
XXXXXXXOX
XXXXXXXOX
XXXXXXXOX
XXXXXXXOO
XXXXXXXOO
XXXXXXXOO
XXXXXXXOO
XXXXXXXOO
XXXXXXXO.
XXXXXXXO.
XXXXXXXO.
XXXXXXXO.
XXX...

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:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 18ms
memory: 3864kb

input:

100000
.XXO..X..
O.XXO.OO.
.OXX.OOXO
OO.XXXXO.
..XO.O.OO
OOOXOO.XO
.OO.OX...
XOX.OOOOO
XOXOO..X.
XOOX.OOX.
O..O..OOO
XOXOOOOOO
...XO.XOX
.XOX.OO..
XX..O..O.
XXXOOO.XO
.OOO.OX.X
X...OXOOX
.X..XXOXX
O..XO.X..
O..XX..OX
OOXOOX.XX
OO.XOX..O
X.OXOOO.X
XOXOO.XX.
OOOXO.OOX
OXO.O...O
OOOXOXX..
..XX.O...
.XX...

output:

-1 -1
-1 -1
-1 -1
1 0
-1 -1
-1 -1
-1 -1
-1 -1
2 2
-1 -1
-1 -1
-1 -1
4 5
-1 -1
47 20
-1 -1
-1 -1
2 3
-1 -1
22 48
11 2
-1 -1
-1 -1
-1 -1
0 1
-1 -1
-1 -1
-1 -1
348 84
3 1
-1 -1
1 0
-1 -1
-1 -1
-1 -1
-1 -1
40 32
-1 -1
1 0
2 0
2 4
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
52 36
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
12...

result:

ok 100000 lines

Test #7:

score: 0
Accepted
time: 14ms
memory: 3784kb

input:

100000
XOO.....O
XXX.X..OO
X.OOOXXXX
X.O...XXX
OXXO.OO.X
OXOX.XXXX
XOXO..XO.
O.OXOXXXX
OXXOXXXXO
X.O.XXX.O
XXX.OXOOO
OX...OOXX
..XXO.OOX
XOOXO....
.OOOXX.X.
OOOXXOOXO
XXX..XOX.
X..OXXO..
..XXX.OX.
XX.X..XO.
...OOOXOX
OO.XO.O..
.O.X.XOXX
OOOX.O.XO
X.O.OXXOO
OOXOX.OX.
O.OO.X.OX
.XXXX...X
.OOXX..OO
.XX...

output:

-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
3 2
-1 -1
-1 -1
-1 -1
-1 -1
2 1
4 1
-1 -1
2 2
-1 -1
-1 -1
13 4
-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
12 2
-1 -1
47 32
-1 -1
3 2
24 44
-1 -1
-1 -1
-1 -1
7 9
-1 -1
-1 -1
1 0
-1 -1
-1 -1
-1 -1
1 0
47 20
-1 -1
4 0
-1 -1
-1 -...

result:

ok 100000 lines

Test #8:

score: 0
Accepted
time: 19ms
memory: 3804kb

input:

100000
O.O.XXXOX
.XX.OXO.X
O..XXXO.X
OXOXXXX..
X.OXO..O.
.OOXOXXO.
OXOXOO..O
OOXOOOOX.
.OX..OOO.
XOOOXXOXO
OOXOX...O
.XOXOXO.O
.XOXO.O.O
OXXXXO.XX
XOXXX.XX.
OX..XOX..
XX..X.XOO
.O..O.O..
OXXXOOXXO
OOX..OXOX
.OX.OXOOO
X.OX.O.XO
XXXX..XOX
OOXXXX.X.
..OXXXX..
XXXX.XX.O
X.XOOXX..
.O..X...O
.OOX.O.OX
OOX...

output:

0 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
12 2
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
0 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
9 5
-1 -1
2 2
-1 -1
-1 -1
8 8
-1 -1
47 20
-1 -1
-1 -1
-1 -1
34 28
-1 -1
-1 -1
-1 -1
8 9
-1 -1
9 5
52 ...

result:

ok 100000 lines

Test #9:

score: 0
Accepted
time: 19ms
memory: 3864kb

input:

100000
.X.XX....
OXOO..XO.
.XXX.O.XO
OOXOX.OO.
OO.OOXOXO
.OXOO.XO.
O.OOX...X
X.OOO.O..
.XO.XOXOX
.XX....O.
XO.XOOX..
.X.OX.OOX
O..XXXOOX
X..XX.O.X
.OOOO..XO
OO...X..O
X.OO..XOX
.XO.O.O.O
.X.OXX.OO
XX..O.O..
..O.O..X.
XO.XO.OOX
O.XXOO.XX
.OOX.OOXX
.X.XXXOOO
OO.XOXXOX
XXX..X..O
XX..X....
.OX.XXO.X
OOX...

output:

-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 0
275 126
-1 -1
3 2
1 0
-1 -1
-1 -1
-1 -1
3 0
-1 -1
2 2
29 36
-1 -1
-1 -1
1 0
-1 -1
-1 -1
0 1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
3 1
3 2
-1 -1
268 236
-1 -1
-1 -1
1 0
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
12 6
-1 -1
2 2
348 84
-1 -1
-1 -1
-1 -1
-1 -1
...

result:

ok 100000 lines

Test #10:

score: 0
Accepted
time: 16ms
memory: 3800kb

input:

100000
.O.OXX.XO
XX..O.OXO
OOXOOX..X
..OXOO.XX
.XOOX.X.X
..O..X...
XX.XXOXO.
OO.OXO...
XOXX.OX.X
XOO..O.OX
.X..XXOOO
X.X.XXO.X
OOOXX.O.O
XX.OX..O.
OOOXO..OX
OO.OXO.XX
XXOOO..XO
XXOOXXXXO
X.XXO.O..
XOXOOXX.X
X.X.OXXOX
OXO.XXXOX
..X..XOXO
.O.X.XXX.
O...OXOOX
.X.XXXXOX
O.XOOOXX.
X..O.XX..
O..XXOXXO
.OO...

output:

2 0
3 2
-1 -1
3 2
-1 -1
1798 1276
-1 -1
-1 -1
-1 -1
-1 -1
0 1
-1 -1
-1 -1
12 2
-1 -1
-1 -1
-1 -1
-1 -1
7 6
-1 -1
-1 -1
-1 -1
8 8
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
52 20
-1 -1
0 1
1438 1652
40 32
-1 -1
-1 -1
-1 -1
-1 -1
2 3
-1 -1
3 0
4 0
-1 -1
-1 -1
-1 -1
-1 -1
-1 ...

result:

ok 100000 lines

Test #11:

score: 0
Accepted
time: 20ms
memory: 3800kb

input:

100000
.XO.XOXX.
XO.X.X.OX
XX..OO..X
.OX.XXOXX
.XOX.XX.X
XXXOO.O..
.O......O
O.OO.XOX.
OXXXOX...
XXO.OX..X
OXXO..XOO
XOXXO.XX.
XXOXXOOOX
OXOXOXXO.
.X.OXXO.O
X..OX....
.XOXO.OOX
OXO....O.
XOXXO.X.O
XO.OXX..O
O.OOOXXOX
.OX.OXXOX
OX..XO.OX
.XOOXXXX.
XXO..OO.X
XX.OOXO.O
..XOOXX.X
XXOX.XXOO
OX.X.OOO.
.O....

output:

-1 -1
-1 -1
8 9
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 0
0 0
2 3
317 48
-1 -1
-1 -1
1 0
2 0
-1 -1
-1 -1
2 0
-1 -1
3 2
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
304 144
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
2 2
-1 -1
-1 -1
-1 -1
2 2
34 28
-1 -1
-1 -1...

result:

ok 100000 lines

Test #12:

score: 0
Accepted
time: 26ms
memory: 3788kb

input:

100000
OX.....OO
O.OXOXXXO
O.XO.X.O.
OOX.OOXO.
XXXO.O.XX
OO..XX.XO
X...XXX.X
.XXOOO..O
X.X.OO.XO
XXXXO.X..
OX..XO.XX
XXOX..OO.
.XX..X...
O.X..O.X.
X.OO.XOXO
..X....O.
X.X.OXOO.
OOOXXOOX.
.O.O.XOXX
O.XO...X.
XXOOOX...
OOXXX.XOO
...O.XX..
.OOOX.X.O
.OXX...XX
XXXXX.XO.
O.X..OX.X
XX.XX...O
X.X.OXO.X
XXO...

output:

-1 -1
0 1
-1 -1
-1 -1
-1 -1
4 1
-1 -1
-1 -1
4 1
-1 -1
-1 -1
2 4
-1 -1
50 28
-1 -1
1902 936
2 2
-1 -1
4 1
40 40
0 2
-1 -1
348 84
-1 -1
-1 -1
-1 -1
12 2
-1 -1
-1 -1
2 0
-1 -1
1 0
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
2 3
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 0
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-...

result:

ok 100000 lines

Test #13:

score: 0
Accepted
time: 20ms
memory: 3760kb

input:

100000
X.X.OO.OX
XOOXX.OOX
X.O..O.XO
O.XXOOX.X
.XOO...OO
.XXXOOXOO
XO.OX.X.O
X.XXO....
.OXXOOXO.
.XOO.XO..
XOXO..XOX
OXOOXOOO.
OX.OX.X.X
XO.O..XXX
.XOO.XOOX
...XX.OOX
.O.X.OOOO
O..X.XXOX
O.OX...OO
OOOO.OXO.
XOXXOXXXO
X.XXXO..O
X.OXO.O..
OO.XXO..X
XXO..XOXX
.OOOOOXOO
OOXXOOOOO
....OOX..
OOOOO.XO.
.OO...

output:

2 3
-1 -1
-1 -1
1 0
-1 -1
1 0
3 0
-1 -1
-1 -1
-1 -1
1 1
-1 -1
-1 -1
-1 -1
-1 -1
14 0
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
2 2
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
3 0
-1 -1
1 1
3 2
-1 -1
0 1
-1 -1
-1 -1
-1 -1
-1 -1
0 1
40 20
-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:

ok 100000 lines

Test #14:

score: 0
Accepted
time: 19ms
memory: 3784kb

input:

100000
XO.OOO.XX
X.OX...X.
XXXX..XX.
.OOO.OXO.
X...OO.XO
.OXO..OXX
.....OOOO
.X..XXO..
.OO...OXO
.OXXX....
O.XXXX.X.
OO.OOX.O.
XOOXOOOXO
OX.XXXX.O
XXXXOX.XO
OX.X.OOX.
XXXXOXOOX
XOOOO...O
XO.X...OO
X.OOO.O..
...X.XXX.
X.XX.OOXO
X...OXOO.
OOXO.O..O
.X.XX.OX.
XXOOXOXXX
..O...OX.
.O.O.XXXX
XXOOOXOO.
O.X...

output:

-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
4 1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
3 0
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 0
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
0 0
-1 -1
-1 -1
1 0
8 5
-1 -1
-1 -1
-1 -1
-1 -1
3 1
-1 -1
-1 -1
-1 -1
2 1
-1 -1
-1 -1
40 28
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -...

result:

ok 100000 lines

Test #15:

score: 0
Accepted
time: 20ms
memory: 3840kb

input:

100000
.XXXX.XXX
OX...XXX.
.OO.O.XX.
XXX.XX..X
OO.O...XO
O.X.O.XO.
XXOOO..O.
XOXXX.X..
.....X.X.
OO..X.X.O
XOOXX.O.O
OXOO.OXX.
.OXXX.OOX
XO.XX.XO.
.O.XOO..X
XOOXXO.OX
.O.OX..X.
OOOOO..OO
.X..O.OOO
.X.O.O.XX
XXXOOXOX.
OOOXOXXOX
.X.OOXOX.
XXXOOXX..
OXO..O.X.
XO.O.XO.O
XXXOOOOX.
O..X.XO.O
XXOO...XX
XO....

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
2 0
-1 -1
-1 -1
-1 -1
58 20
-1 -1
-1 -1
7 7
-1 -1
-1 -1
2 4
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
287 90
-1 -1
-1 -1
-1 -1
1 0
-1 -1
-1 -1
0 2
3 0
-1 -1
-1 -1
1 0
-1 -1
220 248
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1...

result:

ok 100000 lines