QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#235241 | #1811. How to Move the Beans | 11d10xy | WA | 1ms | 6048kb | C++14 | 2.0kb | 2023-11-02 16:23:01 | 2023-11-02 16:23:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
char mp[1010][1010];
int n,m,SG[1010][1010];
struct node_t{
int res[3];
node_t operator+(const node_t&o)const{return{{o.res[res[0]],o.res[res[1]],o.res[res[2]]}};}
};
const node_t I={{0,1,2}};
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%s",mp[i]+1);
for(int i=n;i;i--){
vector<int>mask(m+5);
vector<node_t>trans(m+5,I);
for(int j=1;j<=m;j++)
if(mp[i][j]=='#')trans[j]={{2,2,2}};
else if(i==n||SG[i+1][j]>=2)trans[j]={{1,0,0}};
else if(SG[i+1][j]==1)trans[j]={{2,0,0}};
else trans[j]={{1,2,1}};
int pos=m;while(pos&&mp[i][pos]!='#')pos--;
if(!pos){
vector<node_t>pre(m+5,I),suf(m+5,I);
for(int j=1;j<=m;j++)pre[j]=trans[j]+pre[j-1];
for(int j=m;j;j--)suf[j]=suf[j+1]+trans[j];
for(int j=1;j<=m;j++)
mask[j]|=1<<(pre[j-1]+suf[j+1]).res[2];
for(int j=1;j<=m;j++)pre[j]=pre[j-1]+trans[j];
for(int j=m;j;j--)suf[j]=trans[j]+suf[j+1];
for(int j=1;j<=m;j++)
mask[j]|=1<<(suf[j+1]+pre[j-1]).res[2];
}else{
vector<int>slc;
for(int j=pos+1;;j++){
if(j>m)j=1;
if(mp[i][j]=='#'){
int len=slc.size();
node_t f=I;
for(int k=0;k<len;k++)
mask[slc[k]]|=1<<f.res[2],f=f+trans[slc[k]];
f=I;
for(int k=len-1;k>=0;k--)
mask[slc[k]]|=1<<f.res[2],f=f+trans[slc[k]];
slc.clear();
}else slc.push_back(j);
if(j==pos)break;
}
}
for(int j=1;j<=m;j++)
SG[i][j]=__builtin_ctz(~(mask[j]|1<<(i==n?17:SG[i+1][j])));
}int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mp[i][j]=='B')ans^=SG[i][j];
puts(ans?"A":"B");
}
int main(){
solve();
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 6048kb
input:
2 3 B.# #..
output:
A
result:
wrong answer 1st words differ - expected: 'Alice', found: 'A'