QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#874215#6314. 过河卒L_Hospital_100 ✓551ms94524kbC++142.7kb2025-01-27 20:54:202025-01-27 20:54:21

Judging History

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

  • [2025-01-27 20:54:21]
  • 评测
  • 测评结果:100
  • 用时:551ms
  • 内存:94524kb
  • [2025-01-27 20:54:20]
  • 提交

answer

#include<bits/stdc++.h>
# define rep(i, j, k) for (int i = j; i <= k; ++i)
# define N 1000005
# define nid id[tr][a][b][c][d][e][f]
using namespace std;

int T, n, m, bd[12][12], id[2][12][12][12][12][12][12], cnt, tr, a, b, c, d, e, f, dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}, tx[3] = {-1, 0, 0}, ty[3] = {0, 1, -1};
bool ok[N];
int hd[N], to[6 * N], nxt[6 * N], etimer, deg[N], stat[N], ans[N], stk[N], l, r;
bool pan(int x, int y){return x && x <= n && y && y <= m && !bd[x][y];}
int check(int tr, int a, int b, int c, int d, int e, int f)
{
	if (!pan(a, b) || !pan(c, d) || !pan(e, f)) return -1;
	if (a == c && b == d) return -1;
	if (e == 1) return tr ? -1 : 0;
	if (a == e && b == f || c == e && d == f) return 0;
	return 2;
}
void addedge(int u, int v){if (!v) return; ++deg[u], to[++etimer] = u, nxt[etimer] = hd[v], hd[v] = etimer;}
void bfs()
{
	rep(i, 0, 1000000)
	{
		if (l > r) return;
		int tmp = r;
		rep(t, l, tmp)
		{
			int u = stk[t]; ans[u] = i;
			for (int i = hd[u]; i; i = nxt[i]) if (stat[to[i]] == -1) if (!stat[u]) stat[to[i]] = 1, stk[++r] = to[i]; else if (!--deg[to[i]]) stat[to[i]] = 0, stk[++r] = to[i];
		}
		l = tmp + 1;
	}
}
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	cin >> T >> T;
	while (T--)
	{
		memset(ok, 0, sizeof(ok)); memset(bd, 0, sizeof(bd)), memset(id, 0, sizeof(id)), memset(hd, 0, sizeof(hd)), memset(to, 0, sizeof(to)), memset(nxt, 0, sizeof(nxt));
		memset(deg, 0, sizeof(deg)), memset(stat, -1, sizeof(stat)), memset(ans, 0, sizeof(ans));
		cnt = etimer = r = a = b = c = d = e = f = 0, l = 1;
		cin >> n >> m;
		rep(i, 1, n)
		{
			string s; cin >> s; s = ' ' + s;
			rep(j, 1, m) if (s[j] == '#') bd[i][j] = 1; else if (s[j] == 'O') {if (a) c = i, d = j; else a = i, b = j;} else if (s[j] == 'X') e = i, f = j;
		}
		rep(tr, 0, 1) rep(a, 1, n) rep(b, 1, m) rep(c, 1, n) rep(d, 1, m) rep(e, 1, n) rep(f, 1, m)
		{
			int x = check(tr, a, b, c, d, e, f);
			if (nid || x == -1) continue;
			nid = id[tr][c][d][a][b][e][f] = ++cnt;
			if (!x) stat[nid] = 0, stk[++r] = nid, ok[nid] = 1;
		}
		rep(tr, 0, 1) rep(a, 1, n) rep(b, 1, m) rep(c, 1, n) rep(d, 1, m) rep(e, 1, n) rep(f, 1, m)
		{
			if (!nid || ok[nid]) continue; ok[nid] = 1;
			int tmp = nid;
			if (tr = !tr) rep(i, 0, 3) a += dx[i], b += dy[i], addedge(tmp, nid), a -= dx[i], b -= dy[i], c += dx[i], d += dy[i], addedge(tmp, nid), c -= dx[i], d -= dy[i];
			else rep(i, 0, 2) e += tx[i], f += ty[i], addedge(tmp, nid), e -= tx[i], f -= ty[i];
			tr = !tr;
			if (!deg[nid]) stat[nid] = 0, stk[++r] = nid;
		}
		bfs();
		if (stat[nid] == -1) cout << "Tie\n"; else cout << (stat[nid] ? "Red " : "Black ") << ans[nid] << '\n';
	}
	return 0;
}

詳細信息


Pretests


Final Tests

Test #1:

score: 5
Accepted
time: 322ms
memory: 94332kb

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: 290ms
memory: 94520kb

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: 305ms
memory: 94396kb

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: 247ms
memory: 94240kb

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: 400ms
memory: 94396kb

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: 359ms
memory: 94344kb

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: 58ms
memory: 91268kb

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: 59ms
memory: 91460kb

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: 57ms
memory: 92360kb

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: 348ms
memory: 94520kb

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: 383ms
memory: 94396kb

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: 370ms
memory: 94524kb

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: 377ms
memory: 94392kb

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: 551ms
memory: 94520kb

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: 286ms
memory: 94392kb

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: 294ms
memory: 94524kb

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: 389ms
memory: 94392kb

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: 310ms
memory: 94392kb

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: 327ms
memory: 94352kb

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: 309ms
memory: 94396kb

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