QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#55415 | #2213. Knight | ExplodingKonjac | AC ✓ | 343ms | 76024kb | C++17 | 4.7kb | 2022-10-13 17:08:44 | 2022-10-13 17:08:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
//#define OPENIOBUF
namespace FastIO
{
class FastIOBase
{
protected:
#ifdef OPENIOBUF
static const int BUFSIZE=1<<22;
char buf[BUFSIZE+1];
int buf_p=0;
#endif
FILE *target;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
FastIOBase(FILE *f): target(f){}
~FastIOBase()=default;
};
class FastOutput: public FastIOBase
{
#ifdef OPENIOBUF
public:
inline void flush()
{ fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
protected:
inline void __putc(char x)
{
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE)flush();
#else
putc(x,target);
#endif
}
template<typename T>
inline void __write(T x)
{
static char stk[64],*top;top=stk;
if(x<0) return __putc('-'),__write(-x);
do *(top++)=x%10,x/=10; while(x);
for(;top!=stk;__putc(*(--top)+'0'));
}
public:
FastOutput(FILE *f=stdout): FastIOBase(f){}
#ifdef OPENIOBUF
~FastOutput(){ flush(); }
#endif
template<typename ...T>
inline void writesp(const T &...x)
{ initializer_list<int>{(this->operator<<(x),__putc(' '),0)...}; }
template<typename ...T>
inline void writeln(const T &...x)
{ initializer_list<int>{(this->operator<<(x),__putc('\n'),0)...}; }
inline FastOutput &operator <<(char x)
{ return __putc(x),*this; }
inline FastOutput &operator <<(const char *s)
{ for(;*s;__putc(*(s++)));return *this; }
inline FastOutput &operator <<(const string &s)
{ return (*this)<<s.c_str(); }
template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
inline FastOutput &operator <<(const T &x)
{ return __write(x),*this; }
}qout;
class FastInput: public FastIOBase
{
#ifdef OPENIOBUF
public:
inline void flush()
{ buf[fread(buf,1,BUFSIZE,target)]='\0',buf_p=0; }
#endif
protected:
inline char __getc()
{
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
return buf[buf_p++];
#else
return getc(target);
#endif
}
public:
#ifdef OPENIOBUF
FastInput(FILE *f=stdin): FastIOBase(f){ buf_p=BUFSIZE; }
#else
FastInput(FILE *f=stdin): FastIOBase(f){}
#endif
inline char getchar() { return __getc(); }
template<typename ...T>
inline void read(T &...x)
{ initializer_list<int>{(this->operator>>(x),0)...}; }
inline FastInput &operator >>(char &x)
{ while(isspace(x=__getc()));return *this; }
template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
inline FastInput &operator >>(T &x)
{
static char ch,sym;x=sym=0;
while(isspace(ch=__getc()));
if(ch=='-') sym=1,ch=__getc();
for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=__getc());
return sym?x=-x:x,*this;
}
inline FastInput &operator >>(char *s)
{
while(isspace(*s=__getc()));
for(;!isspace(*s) && *s && ~*s;*(++s)=__getc());
return *s='\0',*this;
}
inline FastInput &operator >>(string &s)
{
char str_buf[(1<<8)+1],*p=str_buf;
char *const buf_end=str_buf+(1<<8);
while(isspace(*p=__getc()));
for(s.clear(),p++;;p=str_buf)
{
for(;p!=buf_end && !isspace(*p=__getc()) && *p && ~*p;p++);
*p='\0',s.append(str_buf);
if(p!=buf_end) break;
}
return *this;
}
}qin;
}
using namespace FastIO;
typedef long long LL;
typedef long double LD;
typedef unsigned int UI;
typedef unsigned long long ULL;
#ifndef DADALZY
#define FILEIO(file) freopen(file".in","r",stdin),freopen(file".out","w",stdout)
#else
#define FILEIO(file)
#endif
int n,m,r,c;
char s[1005][1005];
constexpr int dirs[][2]={{1,1},{1,-1},{-1,1},{-1,-1}};
inline int getId(int i,int j) { return (i-1)*m+j; }
vector<int> g[1000005];
int col[1000005];
void bfs(int u,int now)
{
queue<int> q;
q.push(u),col[u]=now;
while(!q.empty())
{
int u=q.front();
for(auto &v: g[u])
if(!col[v]) col[v]=3-col[u],q.push(v);
q.pop();
}
}
int main()
{
// freopen("input.in","r",stdin);
qin>>n>>m>>r>>c;
for(int i=1;i<=n;i++) qin>>(s[i]+1);
if(!r && !c) return qout<<"Bob",0;
int posa=0,posb=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(s[i][j]=='A') posa=getId(i,j);
if(s[i][j]=='B') posb=getId(i,j);
if(s[i][j]=='@') continue;
for(auto &[dx,dy]: dirs)
{
int x=i+dx*r,y=j+dy*c;
if(x<1 || y<1 || x>n || y>m) continue;
if(s[x][y]=='@') continue;
g[getId(i,j)].push_back(getId(x,y));
}
for(auto &[dx,dy]: dirs)
{
int x=i+dx*c,y=j+dy*r;
if(x<1 || y<1 || x>n || y>m) continue;
if(s[x][y]=='@') continue;
g[getId(i,j)].push_back(getId(x,y));
}
}
if(g[posa].empty()) return qout<<"Bob",0;
bfs(posa,1);
qout<<((!col[posb] || col[posb]==1)?"Alice":"Bob");
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 36ms
memory: 41440kb
Test #2:
score: 0
Accepted
time: 4ms
memory: 27204kb
Test #3:
score: 0
Accepted
time: 94ms
memory: 46436kb
Test #4:
score: 0
Accepted
time: 52ms
memory: 36912kb
Test #5:
score: 0
Accepted
time: 4ms
memory: 27176kb
Test #6:
score: 0
Accepted
time: 15ms
memory: 31200kb
Test #7:
score: 0
Accepted
time: 8ms
memory: 27272kb
Test #8:
score: 0
Accepted
time: 5ms
memory: 28956kb
Test #9:
score: 0
Accepted
time: 35ms
memory: 38084kb
Test #10:
score: 0
Accepted
time: 13ms
memory: 29040kb
Test #11:
score: 0
Accepted
time: 13ms
memory: 28736kb
Test #12:
score: 0
Accepted
time: 49ms
memory: 47860kb
Test #13:
score: 0
Accepted
time: 32ms
memory: 31300kb
Test #14:
score: 0
Accepted
time: 44ms
memory: 40016kb
Test #15:
score: 0
Accepted
time: 16ms
memory: 29120kb
Test #16:
score: 0
Accepted
time: 9ms
memory: 30060kb
Test #17:
score: 0
Accepted
time: 7ms
memory: 27488kb
Test #18:
score: 0
Accepted
time: 23ms
memory: 32164kb
Test #19:
score: 0
Accepted
time: 12ms
memory: 29644kb
Test #20:
score: 0
Accepted
time: 31ms
memory: 38920kb
Test #21:
score: 0
Accepted
time: 8ms
memory: 27864kb
Test #22:
score: 0
Accepted
time: 25ms
memory: 28152kb
Test #23:
score: 0
Accepted
time: 9ms
memory: 27740kb
Test #24:
score: 0
Accepted
time: 6ms
memory: 28016kb
Test #25:
score: 0
Accepted
time: 10ms
memory: 30524kb
Test #26:
score: 0
Accepted
time: 8ms
memory: 29188kb
Test #27:
score: 0
Accepted
time: 4ms
memory: 29112kb
Test #28:
score: 0
Accepted
time: 101ms
memory: 44272kb
Test #29:
score: 0
Accepted
time: 2ms
memory: 29632kb
Test #30:
score: 0
Accepted
time: 20ms
memory: 30048kb
Test #31:
score: 0
Accepted
time: 12ms
memory: 29888kb
Test #32:
score: 0
Accepted
time: 5ms
memory: 27272kb
Test #33:
score: 0
Accepted
time: 85ms
memory: 44952kb
Test #34:
score: 0
Accepted
time: 9ms
memory: 29712kb
Test #35:
score: 0
Accepted
time: 71ms
memory: 42956kb
Test #36:
score: 0
Accepted
time: 76ms
memory: 45744kb
Test #37:
score: 0
Accepted
time: 9ms
memory: 30280kb
Test #38:
score: 0
Accepted
time: 28ms
memory: 31880kb
Test #39:
score: 0
Accepted
time: 3ms
memory: 29448kb
Test #40:
score: 0
Accepted
time: 4ms
memory: 28044kb
Test #41:
score: 0
Accepted
time: 29ms
memory: 32900kb
Test #42:
score: 0
Accepted
time: 16ms
memory: 30548kb
Test #43:
score: 0
Accepted
time: 35ms
memory: 32996kb
Test #44:
score: 0
Accepted
time: 10ms
memory: 28760kb
Test #45:
score: 0
Accepted
time: 4ms
memory: 29052kb
Test #46:
score: 0
Accepted
time: 12ms
memory: 28016kb
Test #47:
score: 0
Accepted
time: 11ms
memory: 30164kb
Test #48:
score: 0
Accepted
time: 88ms
memory: 42648kb
Test #49:
score: 0
Accepted
time: 25ms
memory: 36760kb
Test #50:
score: 0
Accepted
time: 19ms
memory: 32852kb
Test #51:
score: 0
Accepted
time: 189ms
memory: 55872kb
Test #52:
score: 0
Accepted
time: 166ms
memory: 59688kb
Test #53:
score: 0
Accepted
time: 34ms
memory: 33952kb
Test #54:
score: 0
Accepted
time: 250ms
memory: 72576kb
Test #55:
score: 0
Accepted
time: 103ms
memory: 47588kb
Test #56:
score: 0
Accepted
time: 312ms
memory: 67124kb
Test #57:
score: 0
Accepted
time: 122ms
memory: 47284kb
Test #58:
score: 0
Accepted
time: 18ms
memory: 31952kb
Test #59:
score: 0
Accepted
time: 36ms
memory: 33228kb
Test #60:
score: 0
Accepted
time: 278ms
memory: 68792kb
Test #61:
score: 0
Accepted
time: 82ms
memory: 44244kb
Test #62:
score: 0
Accepted
time: 53ms
memory: 39400kb
Test #63:
score: 0
Accepted
time: 229ms
memory: 57704kb
Test #64:
score: 0
Accepted
time: 31ms
memory: 34664kb
Test #65:
score: 0
Accepted
time: 162ms
memory: 73308kb
Test #66:
score: 0
Accepted
time: 35ms
memory: 34528kb
Test #67:
score: 0
Accepted
time: 122ms
memory: 51484kb
Test #68:
score: 0
Accepted
time: 46ms
memory: 36548kb
Test #69:
score: 0
Accepted
time: 300ms
memory: 69976kb
Test #70:
score: 0
Accepted
time: 81ms
memory: 42096kb
Test #71:
score: 0
Accepted
time: 58ms
memory: 41848kb
Test #72:
score: 0
Accepted
time: 25ms
memory: 32436kb
Test #73:
score: 0
Accepted
time: 58ms
memory: 47332kb
Test #74:
score: 0
Accepted
time: 295ms
memory: 66860kb
Test #75:
score: 0
Accepted
time: 84ms
memory: 48968kb
Test #76:
score: 0
Accepted
time: 100ms
memory: 51172kb
Test #77:
score: 0
Accepted
time: 309ms
memory: 60740kb
Test #78:
score: 0
Accepted
time: 33ms
memory: 33224kb
Test #79:
score: 0
Accepted
time: 59ms
memory: 38132kb
Test #80:
score: 0
Accepted
time: 159ms
memory: 52588kb
Test #81:
score: 0
Accepted
time: 73ms
memory: 48632kb
Test #82:
score: 0
Accepted
time: 89ms
memory: 45924kb
Test #83:
score: 0
Accepted
time: 83ms
memory: 43820kb
Test #84:
score: 0
Accepted
time: 35ms
memory: 38288kb
Test #85:
score: 0
Accepted
time: 37ms
memory: 33288kb
Test #86:
score: 0
Accepted
time: 26ms
memory: 33808kb
Test #87:
score: 0
Accepted
time: 32ms
memory: 38620kb
Test #88:
score: 0
Accepted
time: 26ms
memory: 33616kb
Test #89:
score: 0
Accepted
time: 343ms
memory: 66024kb
Test #90:
score: 0
Accepted
time: 100ms
memory: 46612kb
Test #91:
score: 0
Accepted
time: 36ms
memory: 32208kb
Test #92:
score: 0
Accepted
time: 198ms
memory: 68836kb
Test #93:
score: 0
Accepted
time: 51ms
memory: 35296kb
Test #94:
score: 0
Accepted
time: 258ms
memory: 63368kb
Test #95:
score: 0
Accepted
time: 147ms
memory: 67240kb
Test #96:
score: 0
Accepted
time: 87ms
memory: 50464kb
Test #97:
score: 0
Accepted
time: 255ms
memory: 64112kb
Test #98:
score: 0
Accepted
time: 257ms
memory: 60876kb
Test #99:
score: 0
Accepted
time: 109ms
memory: 60908kb
Test #100:
score: 0
Accepted
time: 142ms
memory: 63088kb
Test #101:
score: 0
Accepted
time: 177ms
memory: 73184kb
Test #102:
score: 0
Accepted
time: 173ms
memory: 70316kb
Test #103:
score: 0
Accepted
time: 237ms
memory: 63816kb
Test #104:
score: 0
Accepted
time: 73ms
memory: 41940kb
Test #105:
score: 0
Accepted
time: 144ms
memory: 57232kb
Test #106:
score: 0
Accepted
time: 69ms
memory: 47308kb
Test #107:
score: 0
Accepted
time: 202ms
memory: 62292kb
Test #108:
score: 0
Accepted
time: 285ms
memory: 68192kb
Test #109:
score: 0
Accepted
time: 191ms
memory: 52036kb
Test #110:
score: 0
Accepted
time: 217ms
memory: 66500kb
Test #111:
score: 0
Accepted
time: 158ms
memory: 54340kb
Test #112:
score: 0
Accepted
time: 157ms
memory: 66752kb
Test #113:
score: 0
Accepted
time: 20ms
memory: 32068kb
Test #114:
score: 0
Accepted
time: 29ms
memory: 31300kb
Test #115:
score: 0
Accepted
time: 35ms
memory: 35212kb
Test #116:
score: 0
Accepted
time: 136ms
memory: 66756kb
Test #117:
score: 0
Accepted
time: 192ms
memory: 74844kb
Test #118:
score: 0
Accepted
time: 23ms
memory: 30220kb
Test #119:
score: 0
Accepted
time: 7ms
memory: 29996kb
Test #120:
score: 0
Accepted
time: 188ms
memory: 54700kb
Test #121:
score: 0
Accepted
time: 37ms
memory: 33900kb
Test #122:
score: 0
Accepted
time: 55ms
memory: 47352kb
Test #123:
score: 0
Accepted
time: 29ms
memory: 32916kb
Test #124:
score: 0
Accepted
time: 34ms
memory: 35436kb
Test #125:
score: 0
Accepted
time: 131ms
memory: 46928kb
Test #126:
score: 0
Accepted
time: 34ms
memory: 32084kb
Test #127:
score: 0
Accepted
time: 16ms
memory: 29720kb
Test #128:
score: 0
Accepted
time: 76ms
memory: 52664kb
Test #129:
score: 0
Accepted
time: 39ms
memory: 35588kb
Test #130:
score: 0
Accepted
time: 132ms
memory: 57532kb
Test #131:
score: 0
Accepted
time: 26ms
memory: 31828kb
Test #132:
score: 0
Accepted
time: 175ms
memory: 49848kb
Test #133:
score: 0
Accepted
time: 46ms
memory: 32260kb
Test #134:
score: 0
Accepted
time: 53ms
memory: 41108kb
Test #135:
score: 0
Accepted
time: 294ms
memory: 67492kb
Test #136:
score: 0
Accepted
time: 20ms
memory: 30800kb
Test #137:
score: 0
Accepted
time: 38ms
memory: 34100kb
Test #138:
score: 0
Accepted
time: 322ms
memory: 69144kb
Test #139:
score: 0
Accepted
time: 27ms
memory: 31112kb
Test #140:
score: 0
Accepted
time: 59ms
memory: 45072kb
Test #141:
score: 0
Accepted
time: 138ms
memory: 64964kb
Test #142:
score: 0
Accepted
time: 35ms
memory: 36344kb
Test #143:
score: 0
Accepted
time: 287ms
memory: 70596kb
Test #144:
score: 0
Accepted
time: 113ms
memory: 49828kb
Test #145:
score: 0
Accepted
time: 263ms
memory: 61460kb
Test #146:
score: 0
Accepted
time: 55ms
memory: 40288kb
Test #147:
score: 0
Accepted
time: 177ms
memory: 74952kb
Test #148:
score: 0
Accepted
time: 216ms
memory: 63892kb
Test #149:
score: 0
Accepted
time: 156ms
memory: 58296kb
Test #150:
score: 0
Accepted
time: 303ms
memory: 63984kb
Test #151:
score: 0
Accepted
time: 340ms
memory: 76024kb
Test #152:
score: 0
Accepted
time: 31ms
memory: 32180kb
Test #153:
score: 0
Accepted
time: 40ms
memory: 32592kb
Test #154:
score: 0
Accepted
time: 55ms
memory: 37108kb
Test #155:
score: 0
Accepted
time: 235ms
memory: 58640kb
Test #156:
score: 0
Accepted
time: 61ms
memory: 40228kb
Test #157:
score: 0
Accepted
time: 58ms
memory: 47252kb
Test #158:
score: 0
Accepted
time: 72ms
memory: 44688kb
Test #159:
score: 0
Accepted
time: 24ms
memory: 30628kb
Test #160:
score: 0
Accepted
time: 28ms
memory: 32656kb
Test #161:
score: 0
Accepted
time: 109ms
memory: 42356kb
Test #162:
score: 0
Accepted
time: 38ms
memory: 34536kb
Test #163:
score: 0
Accepted
time: 19ms
memory: 29060kb
Test #164:
score: 0
Accepted
time: 141ms
memory: 52456kb
Test #165:
score: 0
Accepted
time: 227ms
memory: 68928kb
Test #166:
score: 0
Accepted
time: 195ms
memory: 57812kb