QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#413060#4234. Tic Tac Toe CountingDanielChang#AC ✓38ms4188kbC++171.6kb2024-05-17 01:52:222024-05-17 01:52:23

Judging History

This is the latest submission verdict.

  • [2024-05-17 01:52:23]
  • Judged
  • Verdict: AC
  • Time: 38ms
  • Memory: 4188kb
  • [2024-05-17 01:52:22]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

map<string, pair<int,int>> mp;

int check(string &s){
	int cntX=0, cntO=0;
	for(char c : s){
		if(c == 'X') cntX++;
		if(c == 'O') cntO++;
	}
	if(!(cntX == cntO) && !(cntX == cntO+1)) return -2;

	int X=0, O=0;
	for(int i=0; i<9; i+=3){
		if(s[i]==s[i+1] && s[i+1]==s[i+2]){
			if(s[i]=='X') X++;
			if(s[i]=='O') O++;
		}
	}
	for(int i=0; i<3; i++){
		if(s[i]==s[i+3] && s[i+3]==s[i+6]){
			if(s[i]=='X') X++;
			if(s[i]=='O') O++;
		}
	}
	if((s[0]==s[4] && s[4]==s[8]) || (s[2]==s[4] && s[4]==s[6])){
		if(s[4]=='X') X++;
		if(s[4]=='O') O++;
	}
	if(X == 1 && O == 0) return 1;
	if(X == 0 && O == 1) return -1;
	if(X == 2 && O == 0 && cntX == 5) return 1;
	if(X || O) return -2;
	return 0;
}

pair<int,int> dfs(string &s, bool turn){
	if(mp.count(s)) return mp[s];
	int c = check(s);
	assert(c != -2);
	if(c == 1){
		return mp[s] = {1, 0};
	}
	if(c == -1){
		return mp[s] = {0, 1};
	}
	pair<int,int> res{0,0};
	for(int i=0; i<9; i++){
		if(s[i] == '.'){
			s[i] = !turn ? 'X' : 'O';
			auto [X, O] = dfs(s, !turn);
			res.first += X;
			res.second += O;
			s[i]='.';
		}
	}
	return mp[s] = res;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	string s = string(9, '.');
	bool turn = 0;
	dfs(s, turn);
	int t;
	cin >> t;
	while(t--){
		string a;
		cin >> a;
		if(!mp.count(a)){
			cout << -1 << " " << -1 << endl;
		}
		else{
			cout << mp[a].first << " " << mp[a].second << endl;
		}
	}
}
// gcc a.cpp -std=gnu++14 -o a.exe
// g++ a.cpp -g -O2 -std=gnu++14 -static -o a.exe

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 4000kb

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: 32ms
memory: 3956kb

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: 33ms
memory: 3804kb

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: 25ms
memory: 4180kb

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: 24ms
memory: 3804kb

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: 33ms
memory: 4188kb

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: 37ms
memory: 3872kb

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: 34ms
memory: 3936kb

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: 38ms
memory: 4188kb

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: 35ms
memory: 3888kb

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: 38ms
memory: 4136kb

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: 34ms
memory: 3836kb

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: 38ms
memory: 3932kb

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: 35ms
memory: 3804kb

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: 34ms
memory: 3920kb

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