QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#808698#4234. Tic Tac Toe CountingTenshi#AC ✓79ms4316kbC++231.8kb2024-12-11 00:07:102024-12-11 00:07:10

Judging History

This is the latest submission verdict.

  • [2024-12-11 00:07:10]
  • Judged
  • Verdict: AC
  • Time: 79ms
  • Memory: 4316kb
  • [2024-12-11 00:07:10]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
 
#define x first
#define y second
#define int long long
using pii = pair<int, int>;
using ll = long long;
 
inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

// 19683
const int N=1e5+5;

map<string, pii> f;

pii merge(pii a, pii b){
	return {a.x+b.x, a.y+b.y};
}

bool chk(string &s, char c){
	for(int i=0; i<3; i++){
		bool fl=true;
		for(int j=i; j<9; j+=3) if(s[j]!=c) fl=false;
		if(fl) return true;
	}
	
	for(int i=0; i<9; i+=3){
		bool fl=true;
		for(int j=i; j<i+3; j++) if(s[j]!=c) fl=false;
		if(fl) return true;
	}
	
	if(s[0]==s[4] && s[4]==s[8] && s[4]==c) return true;
	if(s[2]==s[4] && s[4]==s[6] && s[4]==c) return true;
	
	return false;
}

int ed(string &s){
	if(chk(s, 'X')) return 1;
	if(chk(s, 'O')) return 2;
	return 0;
}

pii dfs(string s, int cur){
	if(f.count(s)) return f[s];
	int res;
	if(res=ed(s)){
		if(res==1) f[s]={1, 0};
		else f[s]={0, 1};
		return f[s];
	}
	f[s]={0, 0};
	rep(i, 0, 8){
		if(s[i]=='.'){
			string nxt=s;
			if(cur==0) nxt[i]='X';
			else nxt[i]='O';
			f[s]=merge(f[s], dfs(nxt, cur^1));
		}
	}
	
	return f[s];
}

void init(){
	string S=string(9, '.');
	dfs(S, 0);
}

void solve(){
	string s; cin>>s;
	if(f.count(s)){
		auto res=f[s];
		cout<<res.x<<" "<<res.y<<"\n";
	}
	else puts("-1 -1");
}

signed main(){
	init();
	int cs; cin>>cs;
	while(cs--) solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 8ms
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: 78ms
memory: 3988kb

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: 67ms
memory: 3988kb

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

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: 67ms
memory: 4040kb

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: 67ms
memory: 4240kb

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: 68ms
memory: 4112kb

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: 48ms
memory: 4104kb

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

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: 71ms
memory: 4104kb

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: 79ms
memory: 4316kb

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: 67ms
memory: 4104kb

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: 63ms
memory: 3992kb

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: 78ms
memory: 4088kb

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: 72ms
memory: 4308kb

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