QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#229041 | #7635. Fairy Chess | ucup-team987# | WA | 1ms | 3608kb | C++20 | 1.7kb | 2023-10-28 14:53:55 | 2023-10-28 14:53:55 |
Judging History
answer
#include<iostream>
#include<map>
#include<array>
#include<cassert>
using namespace std;
using ull=unsigned long long;
array<ull,64>D[256];
array<ull,64>OR(const array<ull,64>&A,const array<ull,64>&B)
{
array<ull,64>ret;
for(int i=0;i<64;i++)ret[i]=A[i]|B[i];
return ret;
}
string S;
map<ull,bool>memo[13];
bool win(int id,ull mp)
{
if(id==12)
{
return false;
}
assert(id<12);
if(!~mp)return false;
if(memo[id].find(mp)!=memo[id].end())return memo[id][mp];
bool fn=false;
for(int i=0;i<64;i++)if(!(mp>>i&1))
{
ull t=D[S[id]][i];
if((mp&t)==0&&!win(id+1,mp|D[S[id]][i]))
{
fn=true;
break;
}
}
return memo[id][mp]=fn;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
{//B
array<ull,64>&t=D['B'];
for(int i=0;i<8;i++)for(int j=0;j<8;j++)
{
ull now=1uLL<<i*8+j;
for(int x=0;x<8;x++)for(int y=0;y<8;y++)if(abs(x-i)==abs(y-j))now|=1uLL<<x*8+y;
t[i*8+j]=now;
}
}
{//R
array<ull,64>&t=D['R'];
for(int i=0;i<8;i++)for(int j=0;j<8;j++)
{
ull now=1uLL<<i*8+j;
for(int x=0;x<8;x++)for(int y=0;y<8;y++)if(x==i||y==j)now|=1uLL<<x*8+y;
t[i*8+j]=now;
}
}
{//K
array<ull,64>&t=D['K'];
for(int i=0;i<8;i++)for(int j=0;j<8;j++)
{
ull now=1uLL<<i*8+j;
for(int x=0;x<8;x++)for(int y=0;y<8;y++)
{
int dx=abs(x-i),dy=abs(y-j);
if(dx==1&&dy==2||dx==2&&dy==1)now|=1uLL<<x*8+y;
}
t[i*8+j]=now;
}
}
{//Q
array<ull,64>&t=D['Q'];
t=OR(D['B'],D['R']);
}
{//A
array<ull,64>&t=D['A'];
t=OR(D['B'],D['K']);
}
{//C
array<ull,64>&t=D['C'];
t=OR(D['R'],D['K']);
}
{//M
array<ull,64>&t=D['M'];
t=OR(D['Q'],D['K']);
}
cin>>S;
cout<<(win(0,0uLL)?"Alice":"Bob")<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3568kb
input:
BBAARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
BAMBAMQQRCCR
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
QQRAACMRMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
MBBARQRMACQC
output:
Alice
result:
ok single line: 'Alice'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3440kb
input:
ACQCMQRBBRMA
output:
Alice
result:
ok single line: 'Alice'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
MRCMABRQCQAB
output:
Alice
result:
ok single line: 'Alice'
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 3448kb
input:
BBRCMMQAAQRC
output:
Bob
result:
wrong answer 1st lines differ - expected: 'Alice', found: 'Bob'