QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113844#6314. 过河卒Baltinic100 ✓130ms16544kbC++232.0kb2023-06-19 17:55:172023-06-19 17:55:20

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-19 17:55:20]
  • 评测
  • 测评结果:100
  • 用时:130ms
  • 内存:16544kb
  • [2023-06-19 17:55:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
int n,m,N,W;char s[12][12];
int x[104][104][104],y[104][104][104];
int S,T,q[1000004];
void upd(int i,int j,int k,int w){
	if(i>j)swap(i,j);
	if(!y[i][j][k]){
		if(w<0)y[i][j][k]=-w+1;
		else{x[i][j][k]--;if(!x[i][j][k])y[i][j][k]=-w-1;}
		if(y[i][j][k])q[++T]=i<<14|j<<7|k;
	}
}
void solve(){
	scanf("%d%d",&n,&m),N=n*m,S=1,W=T=0;
	int X=-1,Y,Z;
	for(int i=0;i<n;i++){
		scanf("%s",s[i]);
		for(int j=0;j<m;j++){
			if(s[i][j]=='O'||s[i][j]=='X')W^=i^j;
			if(s[i][j]=='O'){if(~X)Y=i*m+j;else X=i*m+j;}
			if(s[i][j]=='X')Z=i*m+j;
		}
	}
	memset(x,0,sizeof(x)),memset(y,0,sizeof(y));
	for(int i=0;i<N;i++)for(int j=i+1;j<N;j++)for(int k=0;k<N;k++){
		int a=i/m,b=i-a*m,c=j/m,d=j-c*m,e=k/m,f=k-e*m;
		bool w=(a^b^c^d^e^f^W)&1;
		if(!e||i==k||j==k)y[i][j][k]=-1;
		else{
			if(w)for(int v=0;v<3;v++){
				int ee=e+dx[v],ff=f+dy[v];
				x[i][j][k]+=~ff&&ff<m&&s[ee][ff]^'#';
			}else for(int v=0;v<4;v++){
				int aa=a+dx[v],bb=b+dy[v],cc=c+dx[v],dd=d+dy[v];
				x[i][j][k]+=~aa&&aa<n&&~bb&&bb<m&&s[aa][bb]^'#'&&aa^c|bb^d;
				x[i][j][k]+=~cc&&cc<n&&~dd&&dd<m&&s[cc][dd]^'#'&&a^cc|b^dd;
			}
			if(!x[i][j][k])y[i][j][k]=-1;
		}
		if(y[i][j][k])q[++T]=i<<14|j<<7|k;
	}
	while(S<=T){
		int u=q[++S],i=u>>14,j=u>>7&127,k=u&127;
		if(i==X&&j==Y&&k==Z)break;
		int a=i/m,b=i-a*m,c=j/m,d=j-c*m,e=k/m,f=k-e*m;
		if(s[a][b]^'#'&&s[c][d]^'#'&&s[e][f]^'#'&&i^j){
			bool w=(a^b^c^d^e^f^W^1)&1;
			if(w)for(int v=1;v<4;v++){
				int ee=e+dx[v],ff=f+dy[v];
				if(ee<n&&~ff&&ff<m)upd(i,j,ee*m+ff,y[i][j][k]);
			}else for(int v=0;v<4;v++){
				int aa=a+dx[v],bb=b+dy[v],cc=c+dx[v],dd=d+dy[v];
				if(~aa&&aa<n&&~bb&&bb<m)upd(aa*m+bb,j,k,y[i][j][k]);
				if(~cc&&cc<n&&~dd&&dd<m)upd(i,cc*m+dd,k,y[i][j][k]);
			}
		}
	}
	if(!y[X][Y][Z])puts("Tie");
	else if(y[X][Y][Z]<0)printf("Black %d\n",-y[X][Y][Z]-1);
	else printf("Red %d\n",y[X][Y][Z]-1);
}
int main(){int id,tc;scanf("%d%d",&id,&tc);while(tc--)solve();}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 86ms
memory: 16256kb

input:

1 10
10 10
.#......#.
..#....#..
#..#..#..#
..#.O..#..
.#......#.
...####...
##..X...##
..........
.##.O####.
..........
10 10
.##..##...
.....##...
..X#.#....
#........#
..#.#.#...
.#...#.#..
#..#.#.#..
..#..#.#.#
...##O#...
..##O#.#..
4 1
O
O
#
X
10 10
.##.....##
...#....##
.#.#...#..
.O###.....
#...

output:

Tie
Black 0
Black 0
Tie
Black 0
Tie
Black 0
Black 0
Tie
Tie

result:

ok 10 lines

Test #2:

score: 5
Accepted
time: 87ms
memory: 16252kb

input:

2 10
10 10
.#.####..#
.##..#####
##.###X###
#....####.
.#.#######
#.#O###.##
..##.####.
..########
##########
##O#.#.###
10 10
..#.###.##
......#..#
....#O....
#..#.....#
...#.#####
.....#..#.
..#.....#O
X#....###.
#.....##..
.#..##....
10 10
.......##.
.O##...##.
..#.......
####..O...
....#...##
.....

output:

Black 0
Tie
Tie
Black 0
Black 0
Tie
Black 0
Tie
Tie
Black 0

result:

ok 10 lines

Test #3:

score: 5
Accepted
time: 82ms
memory: 14340kb

input:

3 10
10 10
##.#######
###..###OO
##X####.##
...#######
#..###...#
##...#####
##..#.####
..##..##.#
###..#.#.#
#.###..##.
10 10
.##..##...
.....##...
..X#.#....
#........#
..#.#.#...
.#...#.#..
#..#.#.#..
..#..#.#.#
...##O#...
..##O#.#..
10 10
..........
.X........
..........
..........
..#.......
.....

output:

Black 0
Black 0
Black 0
Black 0
Black 0
Tie
Tie
Tie
Tie
Tie

result:

ok 10 lines

Test #4:

score: 5
Accepted
time: 81ms
memory: 16308kb

input:

4 10
10 10
.#......#.
..#....#..
#..#..#..#
..#.O..#..
.#......#.
...####...
##..X...##
..........
.##.O####.
..........
10 10
...#.##...
..####.##.
###.######
.####O#.X#
...####..#
.##O#..#.#
##.#..###.
#.#.#....#
.#.#####.#
.##.#.#.##
3 2
OO
##
#X
10 10
.##.##...#
..##..#.#O
.#O#.#...#
#.#.#..##.
...

output:

Tie
Black 0
Black 0
Black 0
Black 0
Black 0
Tie
Tie
Tie
Tie

result:

ok 10 lines

Test #5:

score: 5
Accepted
time: 95ms
memory: 16544kb

input:

5 10
10 10
..........
....O.....
..........
...X......
..........
..........
..........
..........
##########
.......O..
10 10
..........
..O.......
..........
..........
..........
X.........
..........
..........
##########
.......O..
10 1
.
.
.
O
.
.
.
X
#
O
10 1
O
.
.
.
.
.
.
X
#
O
10 10
..........

output:

Red 9
Red 21
Black 12
Red 7
Black 8
Red 23
Black 14
Red 25
Red 23
Red 1

result:

ok 10 lines

Test #6:

score: 5
Accepted
time: 88ms
memory: 16308kb

input:

6 10
10 10
.....O....
..........
..........
..........
..........
.X........
..........
..........
##########
...O......
10 1
O
.
.
.
.
.
.
X
#
O
10 10
..........
..O.......
..........
..........
..........
X.........
..........
..........
##########
.......O..
10 10
..........
.....O....
.............

output:

Red 17
Red 7
Red 21
Red 17
Black 2
Black 12
Black 6
Red 25
Red 23
Black 10

result:

ok 10 lines

Test #7:

score: 5
Accepted
time: 3ms
memory: 12764kb

input:

7 10
10 1
.
O
#
.
.
X
.
#
.
O
10 1
O
.
.
.
.
.
.
X
.
O
10 1
.
.
#
O
O
#
#
.
.
X
5 1
O
O
.
X
.
10 1
O
#
.
.
.
.
.
X
.
O
9 1
O
#
O
.
.
.
.
.
X
10 1
.
.
.
.
X
O
.
#
.
O
10 1
O
O
.
#
.
.
.
.
.
X
10 1
.
.
.
.
.
.
X
.
O
O
10 1
O
.
.
.
#
X
#
O
.
.

output:

Red 5
Red 7
Black 0
Black 2
Red 11
Black 10
Red 1
Red 11
Black 12
Red 1

result:

ok 10 lines

Test #8:

score: 5
Accepted
time: 3ms
memory: 13560kb

input:

8 10
10 1
.
.
#
.
X
#
.
O
#
O
10 1
.
O
O
.
X
.
.
.
.
.
10 1
O
O
.
.
.
.
.
.
.
X
5 1
.
#
O
X
O
10 1
O
#
.
.
.
.
X
.
.
O
9 1
O
#
O
.
.
.
.
X
.
10 1
#
.
.
.
X
O
.
#
.
O
10 1
O
O
#
#
.
.
.
.
.
X
10 1
#
.
.
.
.
.
X
.
O
O
10 1
.
#
O
.
#
O
.
X
#
.

output:

Red 3
Red 3
Red 9
Red 1
Red 9
Red 5
Red 1
Black 0
Red 11
Red 3

result:

ok 10 lines

Test #9:

score: 5
Accepted
time: 6ms
memory: 13676kb

input:

9 10
10 1
#
O
#
.
.
X
.
#
.
O
10 1
O
.
.
.
X
.
.
.
.
O
10 1
.
.
#
O
O
.
#
.
.
X
5 1
O
O
.
X
.
10 1
O
#
.
#
.
.
.
X
.
O
9 1
O
.
#
O
.
.
.
X
.
10 1
.
.
.
.
X
O
.
.
.
O
10 1
O
O
.
#
#
.
.
.
.
X
10 1
.
.
.
.
X
.
#
.
O
O
10 1
.
#
O
#
O
.
.
X
#
.

output:

Red 5
Red 5
Red 5
Black 2
Red 7
Red 5
Red 1
Red 9
Black 8
Red 3

result:

ok 10 lines

Test #10:

score: 5
Accepted
time: 80ms
memory: 13836kb

input:

10 10
10 10
.###..###.
.....O...#
.##.#.....
..##.##.X#
##......#.
#...#.....
....##...#
..#..O##.#
#..#.##...
.....##.#.
10 10
#...##..#.
#......##.
..##....#.
#.#.##..#O
.O...#.##.
.....##.X.
.###......
....#.#.#.
.......##.
###...##.#
10 10
#.#.......
..##..##..
..##.#X..O
....#.....
#..#....#.
#...

output:

Red 7
Red 5
Red 3
Black 2
Red 9
Tie
Tie
Red 9
Red 9
Red 7

result:

ok 10 lines

Test #11:

score: 5
Accepted
time: 82ms
memory: 14272kb

input:

11 10
10 10
...#.....#
..#.......
##.##.###.
##...#.##X
.....#...#
...#.#.O.#
..#...#...
.....#....
......#..#
#...#...O#
10 10
..###O#O#.
.#.###.##.
##..#..#..
....#X....
........##
........##
#...##....
...#..###.
........#.
..#...#.#.
10 10
######...#
O.X.O####.
#.#.#.#...
#.......#.
...##...#.
....

output:

Black 8
Black 0
Black 2
Tie
Tie
Red 9
Tie
Red 9
Red 9
Red 1

result:

ok 10 lines

Test #12:

score: 5
Accepted
time: 89ms
memory: 14216kb

input:

12 10
10 10
##..##..O.
.#........
.#.......#
..........
#.........
.XO##.....
#.........
..........
..........
..........
5 6
#.####
#.####
#.OO##
#X####
######
10 10
....######
.#########
O...##.###
.#########
....######
####....#.
####.####.
####.O..#.
#######.#.
####....#X
10 10
..........
.........

output:

Red 1
Black 2
Red 9
Tie
Red 9
Black 6
Tie
Tie
Red 3
Tie

result:

ok 10 lines

Test #13:

score: 5
Accepted
time: 92ms
memory: 16312kb

input:

13 10
10 10
.##...#...
.#####..##
#..#..#..#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 10
.##......#
..#..##..O
...#.##...
##..#O..##
..#...#...
###.....#X
..#.......
.##.#.#...
.#.#.#..#.
#......#.#
10 10
.........#
..........
O.........
..........
....O.....
....

output:

Black 6
Red 9
Red 9
Red 9
Black 8
Tie
Red 7
Red 7
Tie
Tie

result:

ok 10 lines

Test #14:

score: 5
Accepted
time: 130ms
memory: 16544kb

input:

14 10
10 10
.......O..
..........
..........
O.........
..........
..........
..........
..........
.......X..
..........
10 10
.##...#...
.#####..##
...#..##.#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 10
.#..O...#.
...####...
##.X....##
..........
.#.O..#...
....

output:

Red 27
Black 6
Tie
Black 8
Red 17
Red 63
Black 12
Red 17
Black 16
Red 5

result:

ok 10 lines

Test #15:

score: 5
Accepted
time: 99ms
memory: 14104kb

input:

15 10
10 10
.########O
.........#
########.#
.........#
.#########
..........
#########.
..........
.#########
.......O.X
10 10
.##...#...
.#####..##
...#..##.#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 8
####....
...#..#.
.###..#.
...#.O#.
##.#..#.
...####.
.##...

output:

Black 102
Black 6
Red 13
Red 9
Tie
Red 63
Red 93
Red 139
Red 45
Black 44

result:

ok 10 lines

Test #16:

score: 5
Accepted
time: 111ms
memory: 16304kb

input:

16 10
10 10
....######
.#########
O...##.###
.#########
....######
####....#.
####.####.
####.O..#.
#######.#.
####....#X
10 10
.#..O...#.
...####...
##.X....##
..........
.#.O..#...
.#....#...
.#....#...
..####....
..........
..........
10 10
O#########
#..#..#...
..#..#..##
.#..#..#..
...#..#..#
....

output:

Red 9
Tie
Black 50
Red 333
Red 41
Black 6
Red 133
Black 24
Red 111
Red 101

result:

ok 10 lines

Test #17:

score: 5
Accepted
time: 129ms
memory: 16316kb

input:

17 10
10 10
##########
..........
..........
..########
..........
#########.
.O........
..........
#.........
O#X.......
10 10
.##...#...
.#####..##
...#..##.#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 10
#.......O.
..#.......
...##.##..
..........
..........
....

output:

Black 60
Black 6
Red 53
Red 35
Tie
Tie
Red 9
Red 65
Tie
Red 63

result:

ok 10 lines

Test #18:

score: 5
Accepted
time: 102ms
memory: 16316kb

input:

18 10
10 10
O.........
#..#..###.
.#.##...#.
..X.......
.####.....
.##...##.#
...#..###.
...###..O#
..#..#....
.......###
10 10
...#.....O
........#.
........X.
..........
...#......
..........
.........#
.....O....
..#.......
..........
10 10
..O.#.....
#.#...#...
...#..###.
....#.....
..#..#..#.
#...

output:

Red 159
Tie
Red 73
Black 36
Black 56
Black 6
Red 15
Black 0
Red 63
Black 2

result:

ok 10 lines

Test #19:

score: 5
Accepted
time: 108ms
memory: 15960kb

input:

19 10
10 10
.....#....
...#.#.#.#
#..#.##.#.
.##.....#.
.#..##.#.#
...#......
#.#.#.##..
##...#O##.
..#.#O....
.#...#..X.
10 10
.O....#...
.####....#
.###...#..
..........
###....##.
....#..##.
.#.#.#....
.##.O#..#.
#..#...#..
...#....X#
10 10
O#########
#..#..#...
..#..#..##
.#..#..#..
...#..#..#
....

output:

Black 6
Red 57
Black 50
Red 11
Tie
Red 129
Red 99
Black 0
Red 111
Red 27

result:

ok 10 lines

Test #20:

score: 5
Accepted
time: 101ms
memory: 13844kb

input:

20 10
10 10
.##.....##
...#....##
.#.#...#..
.O###.....
###.......
......###.
.....#..O.
##........
..#...X...
.##.......
10 10
#...#.##..
.O##.....#
#.#.....#.
.#...#....
....#..#..
.###......
....O##.#.
.#.#.....#
..........
.#.#...X#.
10 10
......###.
..#.#..##.
.#.......#
.#.#..###.
..#.#..#..
#...

output:

Tie
Red 63
Red 61
Red 9
Black 6
Black 0
Tie
Red 333
Red 57
Tie

result:

ok 10 lines

Extra Test:

score: 0
Extra Test Passed