QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546979#1811. How to Move the BeanssurguttiWA 5ms14664kbC++172.5kb2024-09-04 16:27:442024-09-04 16:27:46

Judging History

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

  • [2024-09-04 16:27:46]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:14664kb
  • [2024-09-04 16:27:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

const int N = 1000 + 7;
const int inf = 1e9 + 7;

const int T = 1 << 10;

int mex(set<int> S) {
	int res = 0;
	while (S.count(res))
		res++;
	return res;
}

struct Node {
	int L[3], R[3];

	Node(int down = 0) {
		for (int i = 0; i < 3; i++) {
			L[i] = R[i] = mex({down, i});
		}
	}
} tree[T << 1];

Node operator+ (const Node& A, const Node& B) {
	Node C;

	for (int i = 0; i < 3; i++) {
		C.L[i] = B.L[A.L[i]];
		C.R[i] = A.R[B.R[i]];
	}

	return C;
}

void update(int p, int v) {
	tree[p += T] = Node(v);
	for (; p >>= 1; )
		tree[p] = tree[p << 1 | 0] + tree[p << 1 | 1];
}

Node query(int l, int r) {
	Node resL(inf), resR(inf);
	for (l += T, r += T + 1; l < r; l >>= 1, r >>= 1) {
		if (l & 1)
			resL = resL + tree[l++];
		if (r & 1)
			resR = tree[--r] + resR;
	}

	return resL + resR;
}

int h, w;
string s[N];
int l[N][N], r[N][N];
int nim[N][N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> h >> w;
	rep(i, h)	cin >> s[i];

	rep(i, w)	nim[h][i] = inf;

	for (int i = h - 1; i >= 0; i--) {
		int first_hash = -1;
		rep(j, w) {
			if (s[i][j] == '#') {
				first_hash = j;
				break;
				break;
			}
		}

		if (first_hash == -1) {
			rep(j, w) {
				update(j, nim[i + 1][j]);
			}

			rep(j, w) {
				Node u = query(j + 1, w - 1) + query(0, j - 1);
				nim[i][j] = mex({nim[i + 1][j], u.L[2], u.R[2]});
			}
		}
		else {
			{
				l[i][first_hash] = inf;
				int j = first_hash, prv_j = first_hash;
				do {
					j = (j + 1) % w;
					if (s[i][j] == '#') {
						l[i][j] = inf;
					}
					else {
						l[i][j] = mex({l[i][prv_j], nim[i + 1][j]});
					}
					prv_j = j;
				} while (j != first_hash);
			}
			
			{
				r[i][first_hash] = inf;
				int j = first_hash, prv_j = first_hash;
				do {
					j = (j + w - 1) % w;
					if (s[i][j] == '#') {
						r[i][j] = inf;
					}
					else {
						r[i][j] = mex({r[i][prv_j], nim[i + 1][j]});
					}
					prv_j = j;
				} while (j != first_hash);
			}

			rep(j, w) {
				if (s[i][j] == '#')
					nim[i][j] = inf;
				else
					nim[i][j] = mex({nim[i + 1][j], l[i][(j + w - 1) % w], r[i][(j + 1) % w]});
			}
		}
	}

	int ans = 0;

	/*
	cerr << "nim:\n";
	rep(i, h) {
		rep(j, w)
			cerr << nim[i][j] << ' ';
		cerr << '\n';
	}
	*/

	rep(i, h) rep(j, w)
		if (s[i][j] == 'B')
			ans ^= nim[i][j];

	if (ans)
		cout << "Alice\n";
	else
		cout << "Bob\n";

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 3
B.#
#..

output:

Alice

result:

ok "Alice"

Test #2:

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

input:

1 1
B

output:

Bob

result:

ok "Bob"

Test #3:

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

input:

1 3
B#.

output:

Alice

result:

ok "Alice"

Test #4:

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

input:

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

output:

Bob

result:

ok "Bob"

Test #5:

score: 0
Accepted
time: 4ms
memory: 14664kb

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: 8244kb

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: 7920kb

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: -100
Wrong Answer
time: 5ms
memory: 7856kb

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:

Bob

result:

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