QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#235241#1811. How to Move the Beans11d10xyWA 1ms6048kbC++142.0kb2023-11-02 16:23:012023-11-02 16:23:02

Judging History

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

  • [2023-11-02 16:23:02]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6048kb
  • [2023-11-02 16:23:01]
  • 提交

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'