QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#232257 | #1811. How to Move the Beans | kkio | WA | 1ms | 8256kb | C++17 | 2.4kb | 2023-10-30 08:50:56 | 2023-10-30 08:50:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
char s[maxn][maxn];
int Lt[maxn][4],Rt[maxn][4],Lf[maxn][4],Rf[maxn][4],L[maxn],R[maxn];
int f[maxn][maxn];
int n,m;
inline int mex(int a=-1,int b=-1,int c=-1)
{int f1=(a==0||b==0||c==0),f2=(a==1||b==1||c==1),f3=(a==2||b==2||c==2);return f1+(f1&&f2)+(f1&&f2&&f3);}
inline int fixX(int i){return (i-1+n)%n+1;}
inline int fixY(int i){return (i-1+m)%m+1;}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>s[i]+1;
memset(f,-1,sizeof f);
memset(Lt,-1,sizeof Lt);
memset(Rt,-1,sizeof Rt);
memset(Lf,-1,sizeof Lf);
memset(Rf,-1,sizeof Rf);
memset(L,-1,sizeof L);
memset(R,-1,sizeof R);
for(int i=n;i>=1;i--)
{
int flag=0;for(int j=1;j<=m;j++)if(s[i][j]=='#'){flag=j;break;}
if(!flag)
{
for(int k=0;k<=3;k++)Lt[1][k]=Lf[m][k]=Rt[m][k]=Rf[1][k]=k;
for(int j=2;j<=m;j++)for(int k=0;k<=3;k++)Lt[j][k]=mex(Lt[j-1][k],f[i+1][j]);
for(int j=m-1;j>=1;j--)for(int k=0;k<=3;k++)Rt[j][k]=mex(Rt[j+1][k],f[i+1][j]);
for(int j=m-1;j>=1;j--)for(int k=0;k<=3;k++)Lf[j][k]=Lf[j+1][mex(k,f[i+1][j+1])];
for(int j=2;j<=m;j++)for(int k=0;k<=3;k++)Rf[j][k]=Rf[j-1][mex(k,f[i+1][j-1])];
f[i][1]=mex(Lf[2][mex(f[i+1][2])],Rt[2][mex(f[i+1][m])],f[i+1][1]);
f[i][m]=mex(Lt[m-1][mex(f[i+1][1])],Rf[m-1][mex(f[i+1][m-1])],f[i+1][m]);
for(int j=2;j<m;j++)f[i][j]=mex(
Lt[j-1][mex(Lf[j+1][mex(f[i+1][j+1])],f[i+1][1])],
Rt[j+1][mex(Rf[j-1][mex(f[i+1][j-1])],f[i+1][m])],
f[i+1][j]
);
}
else
{
for(int t=1,j=flag;t<=m;t++,j=fixY(j+1))
if(s[i][j]=='#')L[j]=-1;
else L[j]=mex(L[j-1],f[i+1][j]);
for(int t=1,j=flag;t<=m;t++,j=fixY(j-1))
if(s[i][j]=='#')R[j]=-1;
else R[j]=mex(R[j+1],f[i+1][j]);
for(int j=1;j<=m;j++)
if(s[i][j]=='#')f[i][j]=-1;
else f[i][j]=mex(L[fixY(j-1)],R[fixY(j+1)],f[i+1][j]);
}
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(s[i][j]=='B')
ans^=f[i][j];
if(ans)cout<<"Alice"<<'\n';
else cout<<"Bob"<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7792kb
input:
2 3 B.# #..
output:
Alice
result:
ok "Alice"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7660kb
input:
1 1 B
output:
Bob
result:
ok "Bob"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7720kb
input:
1 3 B#.
output:
Alice
result:
ok "Alice"
Test #4:
score: 0
Accepted
time: 1ms
memory: 7760kb
input:
5 18 #.#..#.#..###..### ##...#.#..#.#..#.. #....#.#..###..#.. ##...#.#..#....#.. #.#..###..#....###
output:
Bob
result:
ok "Bob"
Test #5:
score: 0
Accepted
time: 0ms
memory: 7964kb
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: -100
Wrong Answer
time: 1ms
memory: 8256kb
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:
Bob
result:
wrong answer 1st words differ - expected: 'Alice', found: 'Bob'