QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#271407#1811. How to Move the BeanscomplexorWA 4ms8644kbC++173.4kb2023-12-02 11:41:432023-12-02 11:41:43

Judging History

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

  • [2023-12-02 11:41:43]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:8644kb
  • [2023-12-02 11:41:43]
  • 提交

answer

#include <bits/stdc++.h>
typedef long long LL;
typedef unsigned long long ULL;
typedef std::pair<int, int> pii;
#define fi first
#define se second
#define MP std::make_pair
int read()
{
	int s = 0, f = 1;
	char c = getchar();
	while (!(c >= '0' && c <= '9'))
		f ^= (c == '-'), c = getchar();
	while (c >= '0' && c <= '9')
		s = s * 10 + (c - '0'), c = getchar();
	return f ? s : -s; 
}
ULL readull()
{
	ULL s = 0;
	char c = getchar();
	while (!(c >= '0' && c <= '9')) c = getchar();
	while (c >= '0' && c <= '9')
		s = s * 10 + (c - '0'), c = getchar();
	return s; 
}
template<typename T>
void write(T x, char end = '\n')
{
	if (x == 0) return putchar('0'), putchar(end), void();
	if (x < 0) putchar('-'), x = -x;
	static int d[100], cur;
	for (cur = 0; x; x /= 10) d[++cur] = x % 10;
	for (int i = cur; i; i--) putchar('0' + d[i]);
	putchar(end);
}
const int MAXN = 1005;
int n, m, sg[MAXN][MAXN];
int lsg[MAXN], rsg[MAXN];
int lt[4][MAXN], rt[4][MAXN], lf[4][MAXN], rf[4][MAXN];
char s[MAXN][MAXN];
auto nxt = [](int x){ return x == m ? 1 : x + 1; };
auto pre = [](int x){ return x == 1 ? m : x - 1; };
int mex(int x){ return x == 0; }
int mex(int x, int y)
{	
	int res = 0;
	for (; ; res++)
	{
		if (x == res || y == res)
		{ res++; continue; }
		break;
	}
	return res;
}
int mex(int x, int y, int z)
{
	int res = 0;
	for (; ; res++)
	{
		if (x == res || y == res || z == res)
		{ res++; continue; }
		break;
	}
	return res;
}
int main()
{
	n = read(), m = read();
	for (int i = 1; i <= n; i++)
		scanf("%s", s[i] + 1);
	memset(sg, -1, sizeof sg);
	for (int i = n; i; i--)
	{
		int pos = 0;
		for (int j = 1; j <= m; j++)
			if (s[i][j] == '#') { pos = j; break; }
		if (m == 1) sg[i][1] = pos ? -1 : mex(sg[i + 1][1]);
		else if (pos)
		{
			memset(lsg, -1, sizeof lsg);
			memset(rsg, -1, sizeof rsg);
			for (int j = nxt(pos); j != pos; j = nxt(j))
			{
				if (s[i][j] == '#') continue;
				lsg[j] = mex(lsg[pre(j)], sg[i + 1][j]);
			}
			for (int j = pre(pos); j != pos; j = pre(j))
			{
				if (s[i][j] == '#') continue;
				rsg[j] = mex(rsg[nxt(j)], sg[i + 1][j]);
			}
			for (int j = 1; j <= m; j++)
				if (s[i][j] != '#') sg[i][j] = mex(lsg[pre(j)], rsg[nxt(j)], sg[i + 1][j]);
		}
		else
		{
			for (int o = 0; o <= 3; o++)
			{
				lt[o][1] = o;
				for (int j = 2; j <= m; j++)
					lt[o][j] = mex(lt[o][j - 1], sg[i + 1][j]);
				rt[o][m] = o;
				for (int j = m - 1; j; j--)
					rt[o][j] = mex(rt[o][j + 1], sg[i + 1][j]);
			}
			for (int j = 1; j <= m; j++)
				for (int o = 0; o <= 3; o++)
					if (j == 1) rf[o][j] = o;
					else rf[o][j] = rf[mex(o, sg[i + 1][j - 1])][j - 1];
			for (int j = m; j; j--)
				for (int o = 0; o <= 3; o++)
					if (j == m) lf[o][j] = o;
					else lf[o][j] = lf[mex(o, sg[i + 1][j + 1])][j + 1];
			sg[i][1] = mex(sg[i + 1][1], lf[mex(sg[i + 1][2])][2], rt[mex(sg[i + 1][m])][2]);
			sg[i][m] = mex(sg[i + 1][m], lt[mex(sg[i + 1][1])][m - 1], rf[mex(sg[i + 1][m - 1])][m - 1]);
			for (int j = 2; j < m; j++)
			{
				int L = lt[mex(sg[i + 1][1], lf[mex(sg[i + 1][j + 1])][j + 1])][j - 1];
				int R = rt[mex(sg[i + 1][m + 1], rf[mex(sg[i + 1][j - 1])][j - 1])][j + 1];
				sg[i][j] = mex(sg[i + 1][j], L, R);
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (s[i][j] == 'B') ans ^= sg[i][j];
	printf(ans ? "Alice\n" : "Bob\n");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 3
B.#
#..

output:

Alice

result:

ok "Alice"

Test #2:

score: 0
Accepted
time: 2ms
memory: 7544kb

input:

1 1
B

output:

Bob

result:

ok "Bob"

Test #3:

score: 0
Accepted
time: 0ms
memory: 7464kb

input:

1 3
B#.

output:

Alice

result:

ok "Alice"

Test #4:

score: 0
Accepted
time: 2ms
memory: 7724kb

input:

5 18
#.#..#.#..###..###
##...#.#..#.#..#..
#....#.#..###..#..
##...#.#..#....#..
#.#..###..#....###

output:

Bob

result:

ok "Bob"

Test #5:

score: 0
Accepted
time: 1ms
memory: 7740kb

input:

293 249
#B..B..BBB..B.B.B...#BBB..B#B.BBB.#B##B.BB.B.##B#B.BB..B.#B#BB.BB##B#BB#...B..BB..B.B##B.B#B.#.##..B.#..BBBB#.BB..#.BBB#B##BB....B.##B..#...B#..B.BB#B.#...B#.BB.#B#.B...BBB.B.B..B....##.B..B##.BB#B.B.BBB.B#B..#.B.B#.B##..B#.##BB.#BB#.BB.#.B..BB.BB.B
BB.B.#.B#BB.B.B..B.###.B...BB.##.B...B#BB....

output:

Alice

result:

ok "Alice"

Test #6:

score: 0
Accepted
time: 0ms
memory: 8012kb

input:

75 13
BBB.B.BB.B.#B
BB.##...B##BB
..#.B....#.B.
BBB..#...B#BB
#B#.##B..BB..
#B..BBBB.B..#
#B##.BBBBB.B#
BBB.B..#B#B..
.BBB####.##BB
.B##...#.#.#.
#.BB#..B.B.B.
BB#BB.BBB..BB
B.#...#.BBBBB
..#B.BBBB..B#
BB..B..#.....
..B..BBBB.B#.
.B.B##B.#B.##
BBBB#...#..B#
B.BB..BBB#B.B
.#B#B...BB.BB
#.B...BB...B.
...

output:

Alice

result:

ok "Alice"

Test #7:

score: 0
Accepted
time: 0ms
memory: 7504kb

input:

35 38
#.#..B.B.#.BB#.B.B.B..##..B#B###BBB##.
.#.#.B#.#BBB..B..BB.#..BB..##B......#B
B.B#..B..B...##B#B..#.##.#..B.#..B##BB
#.B.B..#..B#.#.B#B##B.BBB..#.B...B..#.
B#.#.BBB..B.BB.B..BBBBB##B..BB#.B#.BB.
B##.B#...B.B.BB.BBB..#BBB.#..#B#.B..#B
B....B#B.#.BBB.B#BB...##B#...B..BB.BB.
..###.#.B#....#.....#...

output:

Alice

result:

ok "Alice"

Test #8:

score: 0
Accepted
time: 2ms
memory: 8644kb

input:

36 106
BB.B..B.BBBB.BB..BB..BB..BB...BB.B..B.B..BBBB.B.BB..B.B..BB..BBBB.B.B.BBBB..B.BBBBBBBBBBBBBBB.BB.B.BBB..BB
#BBB.BBB#..#.BB...###B.B#.B...B.#.BBBB.B..B..#B.#B#BB##.BB.#B..B#B...B....B#B#.#B.B.B.BB#..B#B#.#.#B###.B.
B.BBB.BBBBB.BBB....BB..B.BBBB.BBB.BBB.BBB.B.B.BBB.B...B.B.BBBBB.BBB....BB.BBB.B...

output:

Alice

result:

ok "Alice"

Test #9:

score: -100
Wrong Answer
time: 4ms
memory: 7776kb

input:

245 239
.BBB.BB.B.BBB..B.BB.BBBBBB..B.BBB.B.BBBBBBBBB..B..BB.B.B.BB..B.BB...B.BB.B.BB..BBB..BB..BB.BBB.BBB.BBBBB.BBBB.BB.BBBB...BBB.B..BBBBBBB..BB..B.B.B..BBBBB...BB..BBB...BBB.B..BB.BB.B.BB.BBB..B.B.BBBB.BBBBB.BBB.BBBB.BB...B.B.B...BBB.BBB.BBB..B
B#.#BB..#BB.BBB#..BB..#.B#.##B.BBB###..B#B...BB..#.#...

output:

Alice

result:

wrong answer 1st words differ - expected: 'Bob', found: 'Alice'