QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#235425 | #1811. How to Move the Beans | lefy | WA | 11ms | 8556kb | C++23 | 2.6kb | 2023-11-02 19:11:33 | 2023-11-02 19:11:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N][N];
int n,m;
int get(vector<int>a){
int vis[4];vis[0]=vis[1]=vis[2]=vis[3]=0;
for(int x:a)if(x>=0&&x<=3)vis[x]=1;
for(int i=0;i<4;i++)if(!vis[i])return i;
return -1;
}
int sg[N][N],l[N],r[N],s[N],e[N];
int L1[N][5],L2[N][5],R1[N][5],R2[N][5];
void sol2(int i){
for(int k=0;k<=3;k++)L1[1][k]=R1[m][k]=L2[m][k]=R2[1][k]=k;
for(int j=2;j<=m;j++)for(int k=0;k<=3;k++){
L1[j][k]=get({L1[j-1][k],sg[i+1][j]});
R2[j][k]=R2[j-1][get({k,sg[i+1][j-1]})];
}
for(int j=m-1;j;j--)for(int k=0;k<=3;k++){
L2[j][k]=L2[j+1][get({k,sg[i+1][j+1]})];
R1[j][k]=get({R1[j+1][k],sg[i+1][j]});
// if(i==5)cout<<R1[j][k]<<" ";
}
// cout<<"\n";
for(int j=1;j<=m;j++){
int L=-1,R=-1;
if(m!=1){
if(j==1)L=L2[j+1][get({sg[i+1][j+1]})];
else if(j!=m)L=L1[j-1][get({sg[i+1][1],L2[j+1][get({sg[i+1][j+1]})]})];
else L=L1[j-1][get({sg[i+1][1]})];
if(j==m)R=R2[j-1][get({sg[i+1][j-1]})];
else if(j!=1)R=R1[j+1][get({sg[i+1][m],R2[j-1][get({sg[i+1][j-1]})]})];
else R=R1[j+1][get({sg[i+1][m]})];
}
// if(i==5&&j==3)cout<<L<<" "<<R<<"\n";
sg[i][j]=get({L,R,sg[i+1][j]});
}
}
void sol1(int i){
int st=s[i],ed=e[i];
for(int j=1;j<=m;j++)if(a[i][j]=='#')l[i]=r[i]=-1;
for(int j=st+1;j<=m;j++)if(a[i][j]!='#'){
l[j]=get({l[j-1],sg[i+1][j]});
}
if(a[i][1]!='#'){
l[1]=get({l[m],sg[i+1][1]});
}
for(int j=2;j<st;j++)if(a[i][j]!='#'){
l[j]=get({l[j-1],sg[i+1][j]});
}
for(int j=ed-1;j;j--)if(a[i][j]!='#'){
r[j]=get({r[j+1],sg[i+1][j]});
}
if(a[i][m]!='#'){
r[m]=get({r[1],sg[i+1][m]});
}
for(int j=m-1;j>ed;j--)if(a[i][j]!='#'){
r[j]=get({r[j+1],sg[i+1][j]});
}
for(int j=1;j<=m;j++)if(a[i][j]!='#'){
int le=j-1?j-1:m,ri=j+1<=m?j+1:1;
sg[i][j]=get({sg[i+1][j],l[le],r[ri]});
}else sg[i][j]=4;
}
void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",a[i]+1);
int st=-1,ed=-1;
for(int j=1;j<=m;j++){
if(a[i][j]=='#'){
if(st==-1)st=j;
ed=j;
}
}
s[i]=st,e[i]=ed;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)sg[i][j]=4;
sg[i][0]=sg[i][m+1]=4;
}
for(int j=0;j<=m+1;j++)sg[n+1][j]=4;
int ans=0;
for(int i=n;i;i--){
int st=s[i],ed=e[i];
if(st!=-1)sol1(i);
else sol2(i);
for(int j=1;j<=m;j++)if(a[i][j]=='B')ans^=sg[i][j];
}
// for(int i=1;i<=n;i++){
// // for(int j=1;j<=m;j++)cout<<sg[i][j]<<" ";
// cout<<"\n";
// }
if(ans)printf("Alice\n");
else printf("Bob\n");
}
int main(){
// freopen("chequer.in","r",stdin);
// freopen("chequer.out","w",stdout);
// int t;
// scanf("%d",&t);
// while(t--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5620kb
input:
2 3 B.# #..
output:
Alice
result:
ok "Alice"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
1 1 B
output:
Bob
result:
ok "Bob"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5616kb
input:
1 3 B#.
output:
Alice
result:
ok "Alice"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5664kb
input:
5 18 #.#..#.#..###..### ##...#.#..#.#..#.. #....#.#..###..#.. ##...#.#..#....#.. #.#..###..#....###
output:
Bob
result:
ok "Bob"
Test #5:
score: 0
Accepted
time: 3ms
memory: 5032kb
input:
293 249 #B..B..BBB..B.B.B...#BBB..B#B.BBB.#B##B.BB.B.##B#B.BB..B.#B#BB.BB##B#BB#...B..BB..B.B##B.B#B.#.##..B.#..BBBB#.BB..#.BBB#B##BB....B.##B..#...B#..B.BB#B.#...B#.BB.#B#.B...BBB.B.B..B....##.B..B##.BB#B.B.BBB.B#B..#.B.B#.B##..B#.##BB.#BB#.BB.#.B..BB.BB.B BB.B.#.B#BB.B.B..B.###.B...BB.##.B...B#BB....
output:
Alice
result:
ok "Alice"
Test #6:
score: 0
Accepted
time: 1ms
memory: 4000kb
input:
75 13 BBB.B.BB.B.#B BB.##...B##BB ..#.B....#.B. BBB..#...B#BB #B#.##B..BB.. #B..BBBB.B..# #B##.BBBBB.B# BBB.B..#B#B.. .BBB####.##BB .B##...#.#.#. #.BB#..B.B.B. BB#BB.BBB..BB B.#...#.BBBBB ..#B.BBBB..B# BB..B..#..... ..B..BBBB.B#. .B.B##B.#B.## BBBB#...#..B# B.BB..BBB#B.B .#B#B...BB.BB #.B...BB...B. ...
output:
Alice
result:
ok "Alice"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
35 38 #.#..B.B.#.BB#.B.B.B..##..B#B###BBB##. .#.#.B#.#BBB..B..BB.#..BB..##B......#B B.B#..B..B...##B#B..#.##.#..B.#..B##BB #.B.B..#..B#.#.B#B##B.BBB..#.B...B..#. B#.#.BBB..B.BB.B..BBBBB##B..BB#.B#.BB. B##.B#...B.B.BB.BBB..#BBB.#..#B#.B..#B B....B#B.#.BBB.B#BB...##B#...B..BB.BB. ..###.#.B#....#.....#...
output:
Alice
result:
ok "Alice"
Test #8:
score: 0
Accepted
time: 0ms
memory: 5868kb
input:
36 106 BB.B..B.BBBB.BB..BB..BB..BB...BB.B..B.B..BBBB.B.BB..B.B..BB..BBBB.B.B.BBBB..B.BBBBBBBBBBBBBBB.BB.B.BBB..BB #BBB.BBB#..#.BB...###B.B#.B...B.#.BBBB.B..B..#B.#B#BB##.BB.#B..B#B...B....B#B#.#B.B.B.BB#..B#B#.#.#B###.B. B.BBB.BBBBB.BBB....BB..B.BBBB.BBB.BBB.BBB.B.B.BBB.B...B.B.BBBBB.BBB....BB.BBB.B...
output:
Alice
result:
ok "Alice"
Test #9:
score: -100
Wrong Answer
time: 11ms
memory: 8556kb
input:
245 239 .BBB.BB.B.BBB..B.BB.BBBBBB..B.BBB.B.BBBBBBBBB..B..BB.B.B.BB..B.BB...B.BB.B.BB..BBB..BB..BB.BBB.BBB.BBBBB.BBBB.BB.BBBB...BBB.B..BBBBBBB..BB..B.B.B..BBBBB...BB..BBB...BBB.B..BB.BB.B.BB.BBB..B.B.BBBB.BBBBB.BBB.BBBB.BB...B.B.B...BBB.BBB.BBB..B B#.#BB..#BB.BBB#..BB..#.B#.##B.BBB###..B#B...BB..#.#...
output:
Alice
result:
wrong answer 1st words differ - expected: 'Bob', found: 'Alice'