QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235215 | #1811. How to Move the Beans | c20230201 | WA | 1ms | 7720kb | C++14 | 2.7kb | 2023-11-02 16:09:48 | 2023-11-02 16:09:48 |
Judging History
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'