QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235215#1811. How to Move the Beansc20230201WA 1ms7720kbC++142.7kb2023-11-02 16:09:482023-11-02 16:09:48

Judging History

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

  • [2023-11-02 16:09:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7720kb
  • [2023-11-02 16:09:48]
  • 提交

answer

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

char a[1005][1005];
int sg[1005][1005];
int L[1005], R[1005];
int tl[1005][4], tr[1005][4];// L[m]=t, L[i]=? / R[1]=t, R[i]=?
int pl[1005][4], pr[1005][4];// L[i]=t L[m]=? / R[i]=t, R[1]=?
int pre[1005], nxt[1005];

int mex(int x,int y) {
	int vis[5]={}, res=0;
	vis[x]=vis[y]=1;
	while(vis[res]) ++res;
	return res;
}

int mex(int x,int y,int z) {
	int vis[5]={}, res=0;
	vis[x]=vis[y]=vis[z]=1;
	while(vis[res]) ++res;
	return res;
}

void solve() {
	int n,m; cin>>n>>m;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=m;i++) pre[i]=(i-1), nxt[i]=i+1;
	pre[1]=m, nxt[m]=1;
	for(int i=1;i<=m;i++) sg[n+1][i]=3;
	for(int i=n;i>=1;i--) {
		int flag=0;
		for(int j=1;j<=m;j++) {
			if(a[i][j]=='#') {
				flag=1;
				L[j]=R[j]=3;
				for(int k=pre[j];a[i][k]!='#';k=pre[k]) R[k]=mex(sg[i+1][k],R[nxt[k]]);
				for(int k=nxt[j];a[i][k]!='#';k=nxt[k]) L[k]=mex(sg[i+1][k],L[pre[k]]);
			}
		}
		if(flag) {
			for(int j=1;j<=m;j++) sg[i][j]=mex(sg[i+1][j],L[pre[j]],R[nxt[j]]);
		}else {
			if(m==1) {
				sg[i][1]=(!sg[i+1][1]);
				continue;
			}
			for(int t=0;t<=3;t++) {
				tl[m][t]=t, tr[1][t]=t;
				for(int j=1;j<m;j++) tl[j][t]=mex(tl[pre[j]][t],sg[i+1][j]);
				for(int j=m;j>1;j--) tr[j][t]=mex(tr[nxt[j]][t],sg[i+1][j]);
			}
			for(int t=0;t<=3;t++) pl[m][t]=t, pr[1][t]=t;
			for(int j=m-1;j>=1;j--) {
				for(int t=0;t<=3;t++) {
					int v=mex(t,sg[i+1][j+1]);
					pl[j][t]=pl[j+1][v];
				}
			}
			for(int j=2;j<=m;j++) {
				for(int t=0;t<=3;t++) {
					int v=mex(t,sg[i+1][j-1]);
					pr[j][t]=pr[j-1][v];
				}
			}
			for(int j=1;j<=m;j++) {
				if(j==1) {
					L[2]=(!sg[i+1][2]), R[m]=(!sg[i+1][m]);
					for(int k=3;k<=m;k++) L[k]=mex(L[k-1],sg[i+1][k]);
					for(int k=m-1;k>=2;k--) R[k]=mex(R[k+1],sg[i+1][k]);
					sg[i][j]=mex(sg[i+1][j],R[2],L[m]);
				}else if(j==m) {
					L[1]=(!sg[i+1][1]), R[m-1]=(!sg[i+1][m-1]);
					for(int k=2;k<m;k++) L[k]=mex(L[k-1],sg[i+1][k]);
					for(int k=m-2;k>=1;k--) R[k]=mex(R[k+1],sg[i+1][k]);
					sg[i][j]=mex(sg[i+1][j],R[1],L[m-1]);
				}else {
					int vl=(!sg[i+1][j-1]), vr=(!sg[i+1][j+1]);
					sg[i][j]=mex(sg[i+1][j],tl[j-1][pl[j+1][vr]],tr[j+1][pr[j-1][vl]]);
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			if(a[i][j]=='B') ans^=sg[i][j];
		}
	}
	if(ans) cout<<"A\n";
	else cout<<"B\n";
	return ;
}

int main() {
    // freopen("chequer.in","r",stdin);
    // freopen("chequer.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t=1;
    while(t--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 7720kb

input:

2 3
B.#
#..

output:

A

result:

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