QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234419 | #1811. How to Move the Beans | ExplodingKonjac | WA | 3ms | 8536kb | C++20 | 5.7kb | 2023-11-01 17:04:38 | 2023-11-01 17:04:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
// #define OPENIOBUF
namespace FastIO
{
class FastIOBase
{
protected:
#ifdef OPENIOBUF
static const int BUFSIZE=1<<16;
char buf[BUFSIZE+1];
int buf_p=0;
#endif
FILE *target;
FastIOBase(FILE *f): target(f){}
~FastIOBase()=default;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
};
class FastOutput final: public FastIOBase
{
public:
FastOutput(FILE *f=stdout): FastIOBase(f) {}
#ifdef OPENIOBUF
~FastOutput() { flush(); }
void flush() { fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
void put(char x)
{
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE) flush();
#else
putc(x,target);
#endif
}
FastOutput &operator <<(char x)
{ return put(x),*this; }
FastOutput &operator <<(const char *s)
{ for(;*s;put(*(s++)));return *this; }
FastOutput &operator <<(const std::string &s)
{ return (*this)<<s.c_str(); }
template<typename T>
std::enable_if_t<std::is_integral<T>::value,FastOutput&> operator <<(T x)
{
if(x<0) return put('-'),(*this)<<(-x);
char stk[numeric_limits<T>::digits10+1],*top=stk;
do *(top++)=x%10+'0',x/=10; while(x);
while(top!=stk) put(*(--top));
return *this;
}
template<typename ...T>
void writesp(T &&...x)
{ std::initializer_list<int>{((*this)<<(x),put(' '),0)...}; }
template<typename ...T>
void writeln(T &&...x)
{ std::initializer_list<int>{((*this)<<(x),put('\n'),0)...}; }
template<typename Iter>
void writesp(Iter begin,Iter end)
{ while(begin!=end) (*this)<<*(begin++)<<' '; }
template<typename Iter>
void writeln(Iter begin,Iter end)
{ while(begin!=end) (*this)<<*(begin++)<<'\n'; }
}qout;
class FastInput final: public FastIOBase
{
private:
bool __eof;
public:
FastInput(FILE *f=stdin): FastIOBase(f),__eof(false)
#ifdef OPENIOBUF
{ buf_p=BUFSIZE; }
void flush() { buf[fread(buf,1,BUFSIZE,target)]=EOF,buf_p=0; }
bool eof()const { return buf[buf_p]==EOF; }
#else
{}
bool eof()const { return feof(target); }
#endif
char get()
{
if(__eof) return EOF;
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
char ch=buf[buf_p++];
#else
char ch=getc(target);
#endif
return ~ch?ch:(__eof=true,EOF);
}
void unget(char c)
{
__eof=false;
#ifdef OPENIOBUF
buf[--buf_p]=c;
#else
ungetc(c,target);
#endif
}
explicit operator bool()const { return !__eof; }
FastInput &operator >>(char &x)
{ while(isspace(x=get()));return *this; }
template<typename T>
std::enable_if_t<std::is_integral<T>::value,FastInput&> operator >>(T &x)
{
char ch,sym=0;x=0;
while(isspace(ch=get()));
if(__eof) return *this;
if(ch=='-') sym=1,ch=get();
for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=get());
return unget(ch),sym?x=-x:x,*this;
}
FastInput &operator >>(char *s)
{
while(isspace(*s=get()));
if(__eof) return *this;
for(;!isspace(*s) && !__eof;*(++s)=get());
return unget(*s),*s='\0',*this;
}
FastInput &operator >>(std::string &s)
{
char str_buf[(1<<8)+1]={0},*p=str_buf;
char *const buf_end=str_buf+(1<<8);
while(isspace(*p=get()));
if(__eof) return *this;
for(s.clear(),p++;;p=str_buf)
{
for(;p!=buf_end && !isspace(*p=get()) && !__eof;p++);
if(p!=buf_end) break;
s.append(str_buf);
}
unget(*p),*p='\0',s.append(str_buf);
return *this;
}
template<typename ...T>
void read(T &&...x)
{ std::initializer_list<int>{((*this)>>(x),0)...}; }
template<typename Iter>
void read(Iter begin,Iter end)
{ while(begin!=end) (*this)>>*(begin++); }
}qin;
} // namespace FastIO
using FastIO::qin,FastIO::qout;
using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;
#ifndef DADALZY
#define FILEIO(file) freopen(file".in","r",stdin),freopen(file".out","w",stdout)
#define LOG(...) [](auto...){}(__VA_ARGS__)
#else
#define FILEIO(file)
#define LOG(...) fprintf(stderr,__VA_ARGS__)
#endif
int n,m;
char s[1005][1005];
inline int mex(int x=-1,int y=-1,int z=-1)
{
for(int i=0;;i++)
if(x!=i && y!=i && z!=i)
return i;
}
int sg[1005][1005];
void solve1(int d)
{
static int fl[4][1005],gl[1005][4],fr[4][1005],gr[1005][4];
for(int k=0;k<4;k++)
{
fl[k][1]=mex(sg[d+1][1],k);
for(int i=2;i<=m;i++)
fl[k][i]=mex(fl[k][i-1],sg[d+1][i]);
fr[k][m]=mex(sg[d+1][m],k);
for(int i=m-1;i>=1;i--)
fr[k][i]=mex(fr[k][i+1],sg[d+1][i]);
}
for(int k=0;k<4;k++) gl[m][k]=k,gr[1][k]=1;
for(int i=m-1;i>=1;i--)
for(int k=0;k<4;k++)
gl[i][k]=gl[i+1][mex(k,sg[d+1][i+1])];
for(int i=2;i<=m;i++)
for(int k=0;k<4;k++)
gr[i][k]=gr[i-1][mex(k,sg[d+1][i-1])];
for(int i=1;i<=m;i++)
{
if(s[d][i]=='#') { sg[d][i]=-1;continue; }
int sgL=(i==1?gl[i][3]:fl[gl[i][3]][i-1]),
sgR=(i==m?gr[i][3]:fr[gr[i][3]][i+1]);
sg[d][i]=mex(sgL,sgR,sg[d+1][i]);
}
}
void solve2(int d)
{
static int L[1005],R[1005];
auto pre=[&](int i) { return i==1?m:i-1; };
auto nxt=[&](int i) { return i==m?1:i+1; };
int st=find(s[d]+1,s[d]+n+1,'#')-s[d];
fill(L+1,L+m+1,-1);
for(int i=nxt(st),lst=st;i!=st;lst=i,i=nxt(i))
if(s[d][i]!='#')
L[i]=mex(L[lst],sg[d+1][i]);
fill(R+1,R+m+1,-1);
for(int i=pre(st),lst=st;i!=st;lst=i,i=pre(i))
if(s[d][i]!='#')
R[i]=mex(R[lst],sg[d+1][i]);
for(int i=1;i<=m;i++)
{
if(s[d][i]=='#') { sg[d][i]=-1;continue; }
sg[d][i]=mex(L[pre(i)],R[nxt(i)],sg[d+1][i]);
}
}
int main()
{
qin>>n>>m;
for(int i=1;i<=n;i++) qin>>(s[i]+1);
fill(sg[n+1]+1,sg[n+1]+m+1,-1);
for(int i=n;i>=1;i--)
{
if(m==1)
sg[i][1]=(s[i][1]=='#'?-1:mex(sg[i+1][1]));
else if(count(s[i]+1,s[i]+m+1,'#')==0)
solve1(i);
else solve2(i);
}
int res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(s[i][j]=='B') res^=sg[i][j];
qout<<(res?"Alice":"Bob");
return 0;
}
/*
2 4
B..B
....
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
input:
2 3 B.# #..
output:
Alice
result:
ok "Alice"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
1 1 B
output:
Bob
result:
ok "Bob"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5720kb
input:
1 3 B#.
output:
Alice
result:
ok "Alice"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
5 18 #.#..#.#..###..### ##...#.#..#.#..#.. #....#.#..###..#.. ##...#.#..#....#.. #.#..###..#....###
output:
Bob
result:
ok "Bob"
Test #5:
score: 0
Accepted
time: 0ms
memory: 8376kb
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: 4100kb
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: 0ms
memory: 3856kb
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: 1ms
memory: 5912kb
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: 0
Accepted
time: 3ms
memory: 8536kb
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:
Bob
result:
ok "Bob"
Test #10:
score: 0
Accepted
time: 0ms
memory: 8064kb
input:
288 94 B....BB....BB.BBB.BBBB..B.B.B.....BBBB.B..BBBBBB.B..BBBBBBB....BBB.BBBBB.B.BBBB..B..B.B.BBB..B BB#.#B#BBB.B#BB..BBB.B#BB#B#BB#BBBBBB####.B.B...BBB.BB.B.#.B.B.B.#.B.B.#.#..B..BB..B#..B.#.... BBBBBBB...B.BB.B..BB..BBBB.BBBBB.BBBB..BBBBBB.BB....B.BBBB.BB.BBB..B.BBBB.B.BBBBBB..BBB.BBB.B. .B....B....
output:
Alice
result:
ok "Alice"
Test #11:
score: 0
Accepted
time: 0ms
memory: 4332kb
input:
119 1 B . # . B . # # # . B B # B # # # B # B . . B B B B . B B B B # # . B B B . B . # B B . # B . # . B B B B B B # # B B B # . . # . B B B B . B B . B B B # # B B . # # B B . B . # . B B B B # B . B B . B B . # # B . . . # . . B . . B . . #
output:
Alice
result:
ok "Alice"
Test #12:
score: 0
Accepted
time: 0ms
memory: 6484kb
input:
196 1 . B # . . # B . . . . B B B # . . B # B . B B # . B B . B B B . B . . . B # . . . . . B . B . . . B # B B . . B B # . . # . # B . # . B B . B B B . B B B # . . B . # . . . B . . B B . B . B . . # . . # B B # # . . . B B # . B # B . . # . . . B . . B B # # B . # B # . B . B B . # . . . . # B B ...
output:
Bob
result:
ok "Bob"
Test #13:
score: 0
Accepted
time: 0ms
memory: 6348kb
input:
148 1 . B B . . # B . # . B . . . . B . . . B . B # . # B B . . . B B B # . # . # # . # B . B B B B B . B . . # B B . . . . # . . # B . B . . . B . . . B B . . B . B . . . B B # . . . . B . B . B . . . . # # B . . B . # . # . B # B . . . # . B . B # B B # . B B B . . . . B # B # B B # B # B B B B . B
output:
Alice
result:
ok "Alice"
Test #14:
score: 0
Accepted
time: 1ms
memory: 5656kb
input:
2 5 ...#. .#B..
output:
Alice
result:
ok "Alice"
Test #15:
score: -100
Wrong Answer
time: 1ms
memory: 5764kb
input:
2 4 B..B ....
output:
Alice
result:
wrong answer 1st words differ - expected: 'Bob', found: 'Alice'