QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#65170#4234. Tic Tac Toe CountingSorting#AC ✓303ms19208kbC++1.3kb2022-11-27 21:52:022022-11-27 21:52:04

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-27 21:52:04]
  • Judged
  • Verdict: AC
  • Time: 303ms
  • Memory: 19208kb
  • [2022-11-27 21:52:02]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se sceond
int dp[262144];
vector<int>e[262144];
int res[262144];
int dp1[262144],dp2[262144];
bool vis[262144];
int c[9];
int win(int x,int y,int z){
	int mn=min(c[x],min(c[y],c[z]));
	int mx=max(c[x],max(c[y],c[z]));
	if(mn==mx) return mx;
	else return 0;
}
void dfs(int id){
	if(vis[id]) return;
	vis[id]=true;
	for(auto c:e[id]) dfs(c);
}
int main(){
	ios::sync_with_stdio(false);
	for(int i=(1<<18)-1; i>=0 ;i--){
		int cnt=0;
		for(int j=0; j<9 ;j++){
			c[j]=(i>>(2*j))&3;
			if(c[j]==3){
				res[i]=-1;
				break;
			}
			cnt+=(c[j]!=0);
		}
		int diu=win(0,1,2)+win(3,4,5)+win(6,7,8)+win(0,3,6)+win(1,4,7)+win(2,5,8)+win(0,4,8)+win(2,4,6);
		if(diu>0){//game ends
			if(diu==1) dp1[i]=1;
			else dp2[i]=1;
			continue;
		}
		//build edges
		int nc=1+(cnt%2==0);
		for(int j=0; j<9 ;j++){
			if(c[j]!=0) continue;
			int ni=i|(nc<<(2*j));
			dp1[i]+=dp1[ni];
			dp2[i]+=dp2[ni];
			e[i].push_back(ni);
		}
	}
	dfs(0);
	
	int t;cin >> t;
	while(t--){
		string s;cin >> s;
		int cur=0;
		for(int i=0; i<9 ;i++){
			if(s[i]=='X') cur|=(2<<(2*i));
			if(s[i]=='O') cur|=(1<<(2*i));
		}
		if(!vis[cur]) cout << "-1 -1\n";
		else cout << dp2[cur] << ' ' << dp1[cur] << '\n';
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 27ms
memory: 18208kb

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: 214ms
memory: 18368kb

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: 210ms
memory: 19132kb

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: 267ms
memory: 18708kb

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: 194ms
memory: 18560kb

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: 221ms
memory: 18216kb

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: 287ms
memory: 18280kb

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: 234ms
memory: 18312kb

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: 242ms
memory: 18500kb

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: 256ms
memory: 18232kb

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: 191ms
memory: 18928kb

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: 262ms
memory: 18332kb

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: 231ms
memory: 19208kb

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: 292ms
memory: 18296kb

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: 303ms
memory: 18388kb

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