QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#236062#1811. How to Move the BeansdieselhuangTL 0ms0kbC++142.6kb2023-11-03 15:59:472023-11-03 15:59:52

Judging History

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

  • [2023-11-03 15:59:52]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-11-03 15:59:47]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int n, m, ans = 0, mex[4][4][4], f[1010][1010], fl[1010], fr[1010], gl[1010][3], gr[1010][3], hl[1010][3], hr[1010][3];
char a[1010][1010];
int main()
{
	int i, j, p;
	for(i = 0; i <= 3; i++){
		for(j = 0; j <= 3; j++){
			for(p = 0; p <= 3; p++){
				if(i != 0 && j != 0 && p != 0) mex[i][j][p] = 0;
				else if(i != 1 && j != 1 && p != 1) mex[i][j][p] = 1;
				else if(i != 2 && j != 2 && p != 2) mex[i][j][p] = 2;
				else mex[i][j][p] = 3;
			}
		}
	}
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; i++){
		scanf("%s", a[i] + 1);
	}
	if(m == 1){
		f[n + 1][1] = 3;
		for(i = n; i >= 1; i--){
			if(a[i][1] == '#') f[i][1] = 3;
			else f[i][1] = mex[f[i + 1][1]][3][3];
			if(a[i][1] == 'B') ans ^= f[i][1];
		}
		if(ans > 0) printf("Alice");
		else printf("Bob");
		return 0;
	}
	for(i = 1; i <= m; i++) f[n + 1][i] = 3;
	for(i = n; i >= 1; i--){
		for(j = 1; j <= m; j++){
			if(a[i][j] == '#') break;
		}
		if(j <= m){
			for(p = 1; p <= m; p++){
				if(a[i][p] == '#') fl[p] = 3, fr[p] = 3, f[i][p] = 3;
			}
			for(p = j; p <= m; p++){
				if(a[i][p] != '#') fl[p] = mex[fl[p - 1]][f[i + 1][p]][3];
			}
			fl[0] = fl[m];
			for(p = 1; p < j; p++){
				if(a[i][p] != '#') fl[p] = mex[fl[p - 1]][f[i + 1][p]][3];
			}
			for(p = j; p >= 1; p--){
				if(a[i][p] != '#') fr[p] = mex[fr[p + 1]][f[i + 1][p]][3];
			}
			fr[m + 1] = fr[1];
			for(p = m; p > j; p--){
				if(a[i][p] != '#') fr[p] = mex[fr[p + 1]][f[i + 1][p]][3];
			}
			for(i = 1; i <= m; i++){
				if(a[i][p] != '#') f[i][p] = mex[fl[(p + m - 2) % m + 1]][fr[p % m + 1]][f[i + 1][p]];
			}
		}else{
			for(j = 0; j < 3; j++){
				gl[1][j] = j; gr[m][j] = j; hl[1][j] = j; hr[m][j] = j;
				gl[0][j] = j; gr[m + 1][j] = j; hl[0][j] = 3; hr[m + 1][j] = 3;
				for(p = 2; p <= m; p++) gl[p][j] = mex[gl[p - 1][j]][f[i + 1][p]][3];
				for(p = m - 1; p >= 1; p--) gr[p][j] = mex[gr[p + 1][j]][f[i + 1][p]][3];
			}
			for(p = 2; p <= m; p++){
				for(j = 0; j < 3; j++) hl[p][j] = hl[p - 1][mex[f[i + 1][p - 1]][j][3]];
			}
			for(p = m - 1; p >= 1; p--){
				for(j = 0; j < 3; j++) hr[p][j] = hr[p + 1][mex[f[i + 1][p + 1]][j][3]];
			}
			f[i + 1][0] = f[i + 1][m]; f[i + 1][m + 1] = f[i + 1][1];
			for(p = 1; p <= m; p++){
				fl[p] = gl[p - 1][mex[hr[p + 1][mex[f[i + 1][p + 1]][3][3]]][f[i + 1][1]][3]];
				fr[p] = gr[p + 1][mex[hl[p - 1][mex[f[i + 1][p - 1]][3][3]]][f[i + 1][m]][3]];
				f[i][p] = mex[fl[p]][fr[p]][f[i + 1][p]];
			}
		}
		for(j = 1; j <= m; j++){
			if(a[i][j] == 'B') ans ^= f[i][j];
		}
	}
	if(ans > 0) printf("Alice");
	else printf("Bob");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

2 3
B.#
#..

output:


result: