QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234409 | #1811. How to Move the Beans | ExplodingKonjac | WA | 1ms | 4808kb | C++20 | 5.7kb | 2023-11-01 16:57:18 | 2023-11-01 16:57:19 |
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[i-1],R[i+1],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]+n+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: 1ms
memory: 3404kb
input:
2 3 B.# #..
output:
Alice
result:
ok "Alice"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
1 1 B
output:
Bob
result:
ok "Bob"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3520kb
input:
1 3 B#.
output:
Alice
result:
ok "Alice"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3408kb
input:
5 18 #.#..#.#..###..### ##...#.#..#.#..#.. #....#.#..###..#.. ##...#.#..#....#.. #.#..###..#....###
output:
Bob
result:
ok "Bob"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 4808kb
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:
Bob
result:
wrong answer 1st words differ - expected: 'Alice', found: 'Bob'