QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#234767#1811. How to Move the Beanssinsop90WA 7ms41496kbC++142.5kb2023-11-01 22:01:402023-11-01 22:01:41

Judging History

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

  • [2023-11-01 22:01:41]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:41496kb
  • [2023-11-01 22:01:40]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;
int n, m, Lt[maxn][5], Rt[maxn][5], Lf[maxn][5], Rf[maxn][5], f[maxn][maxn], L[maxn], R[maxn];
char s[maxn][maxn];
int mex(int a = -1, int b = -1, int c = -1) {
	int res = 0;
	if(a == 0 || b == 0 || c == 0) res ++;
	if(a == 1 || b == 1 || c == 1) res ++;
	if(a == 2 || b == 2 || c == 2) res ++;
	return res;
}
int main() {
//	ios::sync_with_stdio(0);
//	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++) cin >> s[i];
	memset(Lt, -1, sizeof(Lt)), memset(Lf, -1, sizeof(Lf)), memset(Rt, -1, sizeof(Rt)), memset(Rf, -1, sizeof(Rf)), memset(f, -1, sizeof(f));
//	cout << Lf
	for(int i = n;i >= 1;i--) {
//		cout << i << '\n';
		int pos = -1;
		for(int j = 0;j < m;j++) if(s[i][j] == '#') pos = j;
		if(pos == -1) {
			
			for(int j = 0;j <= 3;j++) Lt[0][j] = Lf[m - 1][j] = Rt[m - 1][j] = Rf[0][j] = j;
			for(int j = 1;j < m;j++) for(int k = 0;k <= 3;k++) Lt[j][k] = mex(Lt[j - 1][k], f[i + 1][j]);
			for(int j = m - 2;j >= 0;j--) for(int k = 0;k <= 3;k++) Rt[j][k] = mex(Rt[j + 1][k], f[i + 1][j]);
			
			for(int j = m - 2;j >= 0;j--) for(int k = 0;k <= 3;k++) Lf[j][k] = Lt[j + 1][mex(f[i + 1][j + 1], k)];
			for(int j = 1;j < m;j++) for(int k = 0;k <= 3;k++) Rf[j][k] = Rf[j - 1][mex(f[i + 1][j - 1], k)];
			
			f[i][0] = mex(f[i + 1][0], Lf[1][mex(f[i + 1][1])], Rt[1][mex(f[i + 1][m - 1])]);
			
			if(m >= 2) f[i][m - 1] = mex(f[i + 1][m - 1], Lt[m - 2][mex(f[i + 1][0])], Rf[m - 2][mex(f[i + 1][m - 2])]);
//			cout << f[i + 1][m - 1] << " " << Lf[1][mex(f[i + 1][1])] << " " << " " << Rt[1][mex(f[i + 1][m - 1])];
			for(int j = 1;j < m - 1;j++) {
				f[i][j] = mex(f[i + 1][j], Lt[j - 1][mex(Lf[j + 1][mex(f[i + 1][j + 1])], f[i + 1][0])], Rt[j + 1][mex(Rf[j - 1][mex(f[i + 1][j - 1])], f[i + 1][m - 1])]);
			}
		}
		else {
//			cout<< pos << "\n";
			for(int j = pos, t = 1;t <= m;j = (j + 1) % m, t ++) {
				if(s[i][j] == '#') L[j] = -1;
				else L[j] = mex(L[(j - 1 + m) % m], f[i + 1][j]);
//				cout << L[j] << '\n';
			}
			for(int j = pos, t = 1;t <= m;j = (j - 1 + m) % m, t ++) {
//				cout << j << " " << pos << '\n';			
				if(s[i][j] == '#') R[j] = -1;
				else R[j] = mex(R[(j - 1 + m) % m], f[i + 1][j]);
			}
			for(int j = 0;j < m;j++) {
				if(s[i][j] == '#') f[i][j] = -1;
				else f[i][j] = mex(f[i + 1][j], L[(j - 1 + m) % m], R[(j + 1) % m]);
			}
		}
	}
	int ans = 0;
	for(int i = 1;i <= n;i++) {
		for(int j = 0;j < m;j++) {
			if(s[i][j] == 'B') ans ^= f[i][j];
		}
	}
	if(ans) cout << "Alice\n";
	else cout << "Bob\n";
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 39324kb

input:

2 3
B.#
#..

output:

Alice

result:

ok "Alice"

Test #2:

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

input:

1 1
B

output:

Bob

result:

ok "Bob"

Test #3:

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

input:

1 3
B#.

output:

Alice

result:

ok "Alice"

Test #4:

score: 0
Accepted
time: 3ms
memory: 40696kb

input:

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

output:

Bob

result:

ok "Bob"

Test #5:

score: -100
Wrong Answer
time: 7ms
memory: 41496kb

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:

Bob

result:

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