QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#552400#4234. Tic Tac Toe CountingFinderHTAC ✓171ms4324kbC++142.4kb2024-09-07 22:35:082024-09-07 22:35:08

Judging History

This is the latest submission verdict.

  • [2024-09-07 22:35:08]
  • Judged
  • Verdict: AC
  • Time: 171ms
  • Memory: 4324kb
  • [2024-09-07 22:35:08]
  • Submitted

answer

#include<bits/stdc++.h>
#define gt getchar
#define pt putchar
#define int long long
#define ull unsigned long long
#define fst first
#define snd second
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-8;
inline bool pts(char ch){return ch>=48&&ch<=57;}
inline int read(){
	bool f=0;int x=0;char ch;
	ch=gt();
	while(!pts(ch)&&ch!=EOF){if(ch=='-')f=1;ch=gt();}
	while(pts(ch)){x*=10;x+=(ch-48);ch=gt();}
	if(f)return -x;
	else return x;
}
template<class T>
inline void print(T x){
	char s[114];
	int top=0;
	if(x<0)pt('-');
	do{
		top++;
		if(x>=0)s[top]=(x%10)+48;
		else s[top]=(-(x%10)+48);
		x/=10;
	}while(x);
	while(top){pt(s[top]);top--;}
}
map<string,pii>ans;
int getfns(string s){
    //行
    if(s[0]==s[1]&&s[1]==s[2]){
        if(s[0]=='X')return 1;
        else if(s[0]=='O')return 2;
    }
    if(s[4]==s[3]&&s[5]==s[4]){
        if(s[4]=='X')return 1;
        else if(s[4]=='O')return 2;
    }
    if(s[6]==s[7]&&s[7]==s[8]){
        if(s[6]=='X')return 1;
        else if(s[6]=='O')return 2;
    }
    //列
    if(s[0]==s[3]&&s[3]==s[6]){
        if(s[3]=='X')return 1;
        else if(s[3]=='O')return 2;
    }
    if(s[1]==s[4]&&s[4]==s[7]){
        if(s[4]=='X')return 1;
        else if(s[4]=='O')return 2;
    }
    if(s[2]==s[5]&&s[5]==s[8]){
        if(s[2]=='X')return 1;
        else if(s[2]=='O')return 2;
    }
    //对角线
    if(s[0]==s[4]&&s[4]==s[8]){
        if(s[0]=='X')return 1;
        else if(s[0]=='O')return 2;
    }
    if(s[2]==s[4]&&s[4]==s[6]){
        if(s[4]=='X')return 1;
        else if(s[4]=='O')return 2;
    }
    return 0;
}
pii dfs(string s,char ch){
    pii ff;
    int flag=getfns(s);
    //cout<<s<<'\n';
    if(flag){
        if(flag==1)ff.fst=1;
        else ff.snd=1;
        ans[s]=ff;
		return ff;
    }
    for(int i=0;i<9;i++){
        if(s[i]!='.')continue;
        s[i]=ch;
        pii tmp;
        if(ch=='O')tmp=dfs(s,'X');
        else tmp=dfs(s,'O');
        ff.fst+=tmp.fst;
        ff.snd+=tmp.snd;
        s[i]='.';
    }
    ans[s]=ff;
    return ff;
}
signed main(){
    dfs(".........",'X');
    int T=read();
    while(T--){
        string s;
        cin>>s;
        if(!ans.count(s))cout<<-1<<' '<<-1<<'\n';
        else cout<<ans[s].fst<<' '<<ans[s].snd<<'\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 66ms
memory: 4104kb

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: 139ms
memory: 4252kb

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: 160ms
memory: 3984kb

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: 112ms
memory: 4116kb

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: 120ms
memory: 3960kb

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: 142ms
memory: 4324kb

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: 171ms
memory: 4048kb

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: 104ms
memory: 4096kb

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: 115ms
memory: 4056kb

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: 151ms
memory: 4252kb

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: 103ms
memory: 4100kb

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: 128ms
memory: 4052kb

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: 140ms
memory: 4100kb

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: 136ms
memory: 4284kb

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: 136ms
memory: 4324kb

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