QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#55414 | #2213. Knight | ExplodingKonjac | AC ✓ | 366ms | 96896kb | C++17 | 4.6kb | 2022-10-13 17:07:24 | 2022-10-13 17:07:25 |
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 tot,id[1000005],col[1000005];
void dfs(int u,int now)
{
id[u]=tot,col[u]=now;
for(auto &v: g[u])
if(!id[v]) dfs(v,3-now);
}
int main()
{
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));
}
}
for(int i=1;i<=n*m;i++) if(!id[i]) tot++,dfs(i,1);
bool fl=true;
for(auto &v: g[posa]) if(v!=posb) fl=false;
if(fl) return qout<<"Bob",0;
qout<<((id[posa]!=id[posb] || col[posa]==col[posb])?"Alice":"Bob");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 59ms
memory: 45608kb
Test #2:
score: 0
Accepted
time: 2ms
memory: 27236kb
Test #3:
score: 0
Accepted
time: 143ms
memory: 50264kb
Test #4:
score: 0
Accepted
time: 76ms
memory: 39724kb
Test #5:
score: 0
Accepted
time: 5ms
memory: 27004kb
Test #6:
score: 0
Accepted
time: 19ms
memory: 32500kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 27348kb
Test #8:
score: 0
Accepted
time: 14ms
memory: 29320kb
Test #9:
score: 0
Accepted
time: 48ms
memory: 43108kb
Test #10:
score: 0
Accepted
time: 35ms
memory: 33048kb
Test #11:
score: 0
Accepted
time: 9ms
memory: 30264kb
Test #12:
score: 0
Accepted
time: 116ms
memory: 51332kb
Test #13:
score: 0
Accepted
time: 12ms
memory: 31960kb
Test #14:
score: 0
Accepted
time: 50ms
memory: 44492kb
Test #15:
score: 0
Accepted
time: 18ms
memory: 29816kb
Test #16:
score: 0
Accepted
time: 20ms
memory: 32464kb
Test #17:
score: 0
Accepted
time: 4ms
memory: 27512kb
Test #18:
score: 0
Accepted
time: 22ms
memory: 31316kb
Test #19:
score: 0
Accepted
time: 15ms
memory: 28412kb
Test #20:
score: 0
Accepted
time: 24ms
memory: 40204kb
Test #21:
score: 0
Accepted
time: 5ms
memory: 26964kb
Test #22:
score: 0
Accepted
time: 10ms
memory: 29416kb
Test #23:
score: 0
Accepted
time: 4ms
memory: 27268kb
Test #24:
score: 0
Accepted
time: 13ms
memory: 31544kb
Test #25:
score: 0
Accepted
time: 8ms
memory: 29428kb
Test #26:
score: 0
Accepted
time: 15ms
memory: 27212kb
Test #27:
score: 0
Accepted
time: 11ms
memory: 27272kb
Test #28:
score: 0
Accepted
time: 114ms
memory: 50456kb
Test #29:
score: 0
Accepted
time: 9ms
memory: 29724kb
Test #30:
score: 0
Accepted
time: 23ms
memory: 33732kb
Test #31:
score: 0
Accepted
time: 16ms
memory: 31460kb
Test #32:
score: 0
Accepted
time: 14ms
memory: 27300kb
Test #33:
score: 0
Accepted
time: 121ms
memory: 46964kb
Test #34:
score: 0
Accepted
time: 17ms
memory: 30468kb
Test #35:
score: 0
Accepted
time: 129ms
memory: 44804kb
Test #36:
score: 0
Accepted
time: 139ms
memory: 50964kb
Test #37:
score: 0
Accepted
time: 24ms
memory: 30044kb
Test #38:
score: 0
Accepted
time: 42ms
memory: 32504kb
Test #39:
score: 0
Accepted
time: 3ms
memory: 27676kb
Test #40:
score: 0
Accepted
time: 4ms
memory: 28700kb
Test #41:
score: 0
Accepted
time: 16ms
memory: 34684kb
Test #42:
score: 0
Accepted
time: 9ms
memory: 31836kb
Test #43:
score: 0
Accepted
time: 31ms
memory: 36496kb
Test #44:
score: 0
Accepted
time: 3ms
memory: 28312kb
Test #45:
score: 0
Accepted
time: 14ms
memory: 28660kb
Test #46:
score: 0
Accepted
time: 8ms
memory: 27716kb
Test #47:
score: 0
Accepted
time: 15ms
memory: 28976kb
Test #48:
score: 0
Accepted
time: 128ms
memory: 45724kb
Test #49:
score: 0
Accepted
time: 40ms
memory: 41532kb
Test #50:
score: 0
Accepted
time: 21ms
memory: 33832kb
Test #51:
score: 0
Accepted
time: 215ms
memory: 64476kb
Test #52:
score: 0
Accepted
time: 244ms
memory: 66152kb
Test #53:
score: 0
Accepted
time: 64ms
memory: 40896kb
Test #54:
score: 0
Accepted
time: 362ms
memory: 84068kb
Test #55:
score: 0
Accepted
time: 172ms
memory: 52140kb
Test #56:
score: 0
Accepted
time: 346ms
memory: 81688kb
Test #57:
score: 0
Accepted
time: 144ms
memory: 51688kb
Test #58:
score: 0
Accepted
time: 30ms
memory: 39312kb
Test #59:
score: 0
Accepted
time: 53ms
memory: 40728kb
Test #60:
score: 0
Accepted
time: 353ms
memory: 83584kb
Test #61:
score: 0
Accepted
time: 143ms
memory: 50576kb
Test #62:
score: 0
Accepted
time: 122ms
memory: 45664kb
Test #63:
score: 0
Accepted
time: 238ms
memory: 66964kb
Test #64:
score: 0
Accepted
time: 54ms
memory: 40712kb
Test #65:
score: 0
Accepted
time: 289ms
memory: 79016kb
Test #66:
score: 0
Accepted
time: 58ms
memory: 40588kb
Test #67:
score: 0
Accepted
time: 195ms
memory: 56256kb
Test #68:
score: 0
Accepted
time: 60ms
memory: 43320kb
Test #69:
score: 0
Accepted
time: 366ms
memory: 87788kb
Test #70:
score: 0
Accepted
time: 136ms
memory: 46824kb
Test #71:
score: 0
Accepted
time: 129ms
memory: 48688kb
Test #72:
score: 0
Accepted
time: 54ms
memory: 39540kb
Test #73:
score: 0
Accepted
time: 71ms
memory: 53808kb
Test #74:
score: 0
Accepted
time: 356ms
memory: 81968kb
Test #75:
score: 0
Accepted
time: 178ms
memory: 54684kb
Test #76:
score: 0
Accepted
time: 192ms
memory: 56852kb
Test #77:
score: 0
Accepted
time: 305ms
memory: 71724kb
Test #78:
score: 0
Accepted
time: 52ms
memory: 39396kb
Test #79:
score: 0
Accepted
time: 82ms
memory: 44960kb
Test #80:
score: 0
Accepted
time: 181ms
memory: 57128kb
Test #81:
score: 0
Accepted
time: 143ms
memory: 55108kb
Test #82:
score: 0
Accepted
time: 138ms
memory: 52400kb
Test #83:
score: 0
Accepted
time: 149ms
memory: 51448kb
Test #84:
score: 0
Accepted
time: 92ms
memory: 44556kb
Test #85:
score: 0
Accepted
time: 43ms
memory: 40084kb
Test #86:
score: 0
Accepted
time: 53ms
memory: 40244kb
Test #87:
score: 0
Accepted
time: 62ms
memory: 44496kb
Test #88:
score: 0
Accepted
time: 60ms
memory: 40260kb
Test #89:
score: 0
Accepted
time: 354ms
memory: 80796kb
Test #90:
score: 0
Accepted
time: 151ms
memory: 52688kb
Test #91:
score: 0
Accepted
time: 50ms
memory: 39844kb
Test #92:
score: 0
Accepted
time: 335ms
memory: 76136kb
Test #93:
score: 0
Accepted
time: 63ms
memory: 42720kb
Test #94:
score: 0
Accepted
time: 309ms
memory: 75944kb
Test #95:
score: 0
Accepted
time: 217ms
memory: 73648kb
Test #96:
score: 0
Accepted
time: 189ms
memory: 56368kb
Test #97:
score: 0
Accepted
time: 286ms
memory: 79576kb
Test #98:
score: 0
Accepted
time: 271ms
memory: 68892kb
Test #99:
score: 0
Accepted
time: 256ms
memory: 66728kb
Test #100:
score: 0
Accepted
time: 256ms
memory: 68336kb
Test #101:
score: 0
Accepted
time: 321ms
memory: 79656kb
Test #102:
score: 0
Accepted
time: 254ms
memory: 77488kb
Test #103:
score: 0
Accepted
time: 318ms
memory: 76184kb
Test #104:
score: 0
Accepted
time: 101ms
memory: 45700kb
Test #105:
score: 0
Accepted
time: 243ms
memory: 63808kb
Test #106:
score: 0
Accepted
time: 137ms
memory: 55036kb
Test #107:
score: 0
Accepted
time: 283ms
memory: 72416kb
Test #108:
score: 0
Accepted
time: 328ms
memory: 83052kb
Test #109:
score: 0
Accepted
time: 211ms
memory: 59396kb
Test #110:
score: 0
Accepted
time: 323ms
memory: 76012kb
Test #111:
score: 0
Accepted
time: 218ms
memory: 60240kb
Test #112:
score: 0
Accepted
time: 347ms
memory: 72992kb
Test #113:
score: 0
Accepted
time: 56ms
memory: 39700kb
Test #114:
score: 0
Accepted
time: 49ms
memory: 39036kb
Test #115:
score: 0
Accepted
time: 67ms
memory: 41136kb
Test #116:
score: 0
Accepted
time: 265ms
memory: 73344kb
Test #117:
score: 0
Accepted
time: 363ms
memory: 80724kb
Test #118:
score: 0
Accepted
time: 17ms
memory: 37936kb
Test #119:
score: 0
Accepted
time: 27ms
memory: 37792kb
Test #120:
score: 0
Accepted
time: 261ms
memory: 66264kb
Test #121:
score: 0
Accepted
time: 66ms
memory: 41720kb
Test #122:
score: 0
Accepted
time: 183ms
memory: 56652kb
Test #123:
score: 0
Accepted
time: 78ms
memory: 40816kb
Test #124:
score: 0
Accepted
time: 80ms
memory: 43180kb
Test #125:
score: 0
Accepted
time: 141ms
memory: 51156kb
Test #126:
score: 0
Accepted
time: 46ms
memory: 39832kb
Test #127:
score: 0
Accepted
time: 33ms
memory: 37512kb
Test #128:
score: 0
Accepted
time: 108ms
memory: 60504kb
Test #129:
score: 0
Accepted
time: 59ms
memory: 43516kb
Test #130:
score: 0
Accepted
time: 252ms
memory: 63300kb
Test #131:
score: 0
Accepted
time: 52ms
memory: 39528kb
Test #132:
score: 0
Accepted
time: 203ms
memory: 59572kb
Test #133:
score: 0
Accepted
time: 53ms
memory: 40184kb
Test #134:
score: 0
Accepted
time: 97ms
memory: 48752kb
Test #135:
score: 0
Accepted
time: 354ms
memory: 83752kb
Test #136:
score: 0
Accepted
time: 33ms
memory: 38540kb
Test #137:
score: 0
Accepted
time: 47ms
memory: 41848kb
Test #138:
score: 0
Accepted
time: 328ms
memory: 85860kb
Test #139:
score: 0
Accepted
time: 51ms
memory: 38952kb
Test #140:
score: 0
Accepted
time: 107ms
memory: 52948kb
Test #141:
score: 0
Accepted
time: 311ms
memory: 71564kb
Test #142:
score: 0
Accepted
time: 90ms
memory: 44096kb
Test #143:
score: 0
Accepted
time: 359ms
memory: 87960kb
Test #144:
score: 0
Accepted
time: 191ms
memory: 54364kb
Test #145:
score: 0
Accepted
time: 252ms
memory: 69148kb
Test #146:
score: 0
Accepted
time: 106ms
memory: 46352kb
Test #147:
score: 0
Accepted
time: 345ms
memory: 82860kb
Test #148:
score: 0
Accepted
time: 275ms
memory: 73580kb
Test #149:
score: 0
Accepted
time: 253ms
memory: 63040kb
Test #150:
score: 0
Accepted
time: 306ms
memory: 75500kb
Test #151:
score: 0
Accepted
time: 342ms
memory: 96896kb
Test #152:
score: 0
Accepted
time: 56ms
memory: 39952kb
Test #153:
score: 0
Accepted
time: 44ms
memory: 40412kb
Test #154:
score: 0
Accepted
time: 86ms
memory: 44836kb
Test #155:
score: 0
Accepted
time: 272ms
memory: 71736kb
Test #156:
score: 0
Accepted
time: 84ms
memory: 47876kb
Test #157:
score: 0
Accepted
time: 75ms
memory: 55020kb
Test #158:
score: 0
Accepted
time: 147ms
memory: 52600kb
Test #159:
score: 0
Accepted
time: 36ms
memory: 38548kb
Test #160:
score: 0
Accepted
time: 50ms
memory: 40668kb
Test #161:
score: 0
Accepted
time: 124ms
memory: 48328kb
Test #162:
score: 0
Accepted
time: 64ms
memory: 42240kb
Test #163:
score: 0
Accepted
time: 29ms
memory: 36996kb
Test #164:
score: 0
Accepted
time: 232ms
memory: 58552kb
Test #165:
score: 0
Accepted
time: 343ms
memory: 78716kb
Test #166:
score: 0
Accepted
time: 278ms
memory: 69772kb