QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#226966 | #7635. Fairy Chess | PhantomThreshold# | AC ✓ | 1171ms | 139804kb | C++20 | 2.5kb | 2023-10-26 19:14:35 | 2023-10-26 19:14:35 |
Judging History
answer
#include <bits/stdc++.h>
#define ull unsigned long long
//#define int long long
using namespace std;
const int maxn = 10;
const int maxt = 6;
ull bit[8][8];
int check(const int x,const int y) { return x>=0 && y>=0 && x<8 && y<8; }
ull bishop(const int x,const int y)
{
ull ret=bit[x][y];
for(int i=x-1,j=y-1;i>=0&&j>=0;i--,j--)
ret|= bit[i][j];
for(int i=x-1,j=y+1;i>=0&&j<8;i--,j++)
ret|= bit[i][j];
for(int i=x+1,j=y-1;i<8&&j>=0;i++,j--)
ret|= bit[i][j];
for(int i=x+1,j=y+1;i<8&&j<8;i++,j++)
ret|= bit[i][j];
return ret;
}
ull rook(const int x,const int y)
{
ull ret=bit[x][y];
for(int i=x,j=y-1;j>=0;j--)
ret|= bit[i][j];
for(int i=x,j=y+1;j<8;j++)
ret|= bit[i][j];
for(int j=y,i=x-1;i>=0;i--)
ret|= bit[i][j];
for(int j=y,i=x+1;i<8;i++)
ret|=bit[i][j];
return ret;
}
ull queen(const int x,const int y)
{
ull ret=bit[x][y];
ret|= bishop(x,y);
ret|= rook(x,y);
return ret;
}
int dx[]={-2,-2,-1,-1,+1,+1,+2,+2};
int dy[]={-1,+1,-2,+2,-2,+2,-1,+1};
ull knight(const int x,const int y)
{
ull ret=bit[x][y];
for(int dir=0;dir<8;dir++)
{
int i=x+dx[dir];
int j=y+dy[dir];
if(check(i,j))
ret|=bit[i][j];
}
return ret;
}
ull occupy(const int ty,const int x,const int y)
{
ull ret= bit[x][y];
if(ty%3==0) ret|=bishop(x,y);
if(ty%3==1) ret|=rook(x,y);
if(ty%3==2) ret|=queen(x,y);
if(ty>=3) ret|=knight(x,y);
return ret;
}
ull v[maxt][maxn][maxn];
void pre()
{
for(int i=0;i<8;i++) for(int j=0;j<8;j++)
bit[i][j]= (1llu)<<(i*8+j);
for(int t=0;t<maxt;t++) for(int i=0;i<8;i++) for(int j=0;j<8;j++)
v[t][i][j]= occupy(t,i,j);
}
int id[1000];
string str;
map< tuple<int,ull,ull>, int >mp;
int solve(const int pos,const ull S,const ull capS)
{
const auto temp= make_tuple(pos,S,capS);
if(mp.count(temp)!=0) return mp[temp];
int ty=id[(int)str[pos]];
int ok=0;
for(int i=0;i<8 && ok==0;i++) for(int j=0;j<8 && ok==0;j++) if( !(capS>>(i*8+j)&1llu) )
{
if( (v[ty][i][j]&S)==0llu )
{
if( !solve(pos+1,S|bit[i][j],capS|v[ty][i][j]) )
{
ok=1;
break;
}
}
}
return mp[temp]=ok;
}
signed main()
{
//freopen("tmp.in","r",stdin);
ios_base::sync_with_stdio(false);
//cin.tie(0);
id['B']=0, id['R']=1, id['Q']=2;
id['A']=3, id['C']=4, id['M']=5;
//0:bishop 1:rook 2:queen
//0~2, 3~5:knight
pre();
cin>>str;
int ok= solve(0,0,0);
if(ok) cout<<"Alice\n";
else cout<<"Bob\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 104ms
memory: 21384kb
input:
BBAARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 3ms
memory: 5036kb
input:
BAMBAMQQRCCR
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: 0
Accepted
time: 3ms
memory: 4336kb
input:
QQRAACMRMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #4:
score: 0
Accepted
time: 13ms
memory: 6124kb
input:
MBBARQRMACQC
output:
Alice
result:
ok single line: 'Alice'
Test #5:
score: 0
Accepted
time: 4ms
memory: 4264kb
input:
ACQCMQRBBRMA
output:
Alice
result:
ok single line: 'Alice'
Test #6:
score: 0
Accepted
time: 8ms
memory: 5216kb
input:
MRCMABRQCQAB
output:
Alice
result:
ok single line: 'Alice'
Test #7:
score: 0
Accepted
time: 14ms
memory: 6296kb
input:
BBRCMMQAAQRC
output:
Alice
result:
ok single line: 'Alice'
Test #8:
score: 0
Accepted
time: 9ms
memory: 6116kb
input:
RRMCQMACABQB
output:
Alice
result:
ok single line: 'Alice'
Test #9:
score: 0
Accepted
time: 10ms
memory: 6280kb
input:
QMQBMRBACACR
output:
Alice
result:
ok single line: 'Alice'
Test #10:
score: 0
Accepted
time: 7ms
memory: 5016kb
input:
CMRQAQCBBRAM
output:
Alice
result:
ok single line: 'Alice'
Test #11:
score: 0
Accepted
time: 13ms
memory: 6984kb
input:
CABCRQMMRQAB
output:
Alice
result:
ok single line: 'Alice'
Test #12:
score: 0
Accepted
time: 40ms
memory: 11452kb
input:
ARCBBCMQRAQM
output:
Alice
result:
ok single line: 'Alice'
Test #13:
score: 0
Accepted
time: 2ms
memory: 4028kb
input:
ARCMCARMQBBQ
output:
Alice
result:
ok single line: 'Alice'
Test #14:
score: 0
Accepted
time: 28ms
memory: 9072kb
input:
AQABMCQCMRRB
output:
Bob
result:
ok single line: 'Bob'
Test #15:
score: 0
Accepted
time: 7ms
memory: 5156kb
input:
ACMRABRQMCBQ
output:
Alice
result:
ok single line: 'Alice'
Test #16:
score: 0
Accepted
time: 30ms
memory: 10696kb
input:
CBARMBCQMQAR
output:
Bob
result:
ok single line: 'Bob'
Test #17:
score: 0
Accepted
time: 45ms
memory: 11588kb
input:
RBABRQMCAMQC
output:
Bob
result:
ok single line: 'Bob'
Test #18:
score: 0
Accepted
time: 2ms
memory: 4040kb
input:
MBCQBQARRMCA
output:
Alice
result:
ok single line: 'Alice'
Test #19:
score: 0
Accepted
time: 25ms
memory: 8296kb
input:
AMBQRBCQACMR
output:
Bob
result:
ok single line: 'Bob'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
QRAMQMBBCRAC
output:
Alice
result:
ok single line: 'Alice'
Test #21:
score: 0
Accepted
time: 5ms
memory: 4632kb
input:
ARBCQMMBARQC
output:
Alice
result:
ok single line: 'Alice'
Test #22:
score: 0
Accepted
time: 80ms
memory: 17216kb
input:
CACAMBRQQRBM
output:
Bob
result:
ok single line: 'Bob'
Test #23:
score: 0
Accepted
time: 30ms
memory: 9064kb
input:
CQRRMMBQABCA
output:
Bob
result:
ok single line: 'Bob'
Test #24:
score: 0
Accepted
time: 21ms
memory: 8292kb
input:
ABABCQRMMCRQ
output:
Alice
result:
ok single line: 'Alice'
Test #25:
score: 0
Accepted
time: 11ms
memory: 6612kb
input:
CMBRAAQRQMBC
output:
Bob
result:
ok single line: 'Bob'
Test #26:
score: 0
Accepted
time: 2ms
memory: 3996kb
input:
AQBMRMQRBACC
output:
Alice
result:
ok single line: 'Alice'
Test #27:
score: 0
Accepted
time: 16ms
memory: 7312kb
input:
BRACQQMCAMBR
output:
Bob
result:
ok single line: 'Bob'
Test #28:
score: 0
Accepted
time: 6ms
memory: 4988kb
input:
MCCAQBMQRABR
output:
Bob
result:
ok single line: 'Bob'
Test #29:
score: 0
Accepted
time: 37ms
memory: 10948kb
input:
RBQBCRAACMQM
output:
Bob
result:
ok single line: 'Bob'
Test #30:
score: 0
Accepted
time: 10ms
memory: 6160kb
input:
ACRQARMBBQMC
output:
Bob
result:
ok single line: 'Bob'
Test #31:
score: 0
Accepted
time: 2ms
memory: 3976kb
input:
MRCQBCBQRMAA
output:
Alice
result:
ok single line: 'Alice'
Test #32:
score: 0
Accepted
time: 11ms
memory: 6532kb
input:
ACRQQCMMBBAR
output:
Bob
result:
ok single line: 'Bob'
Test #33:
score: 0
Accepted
time: 6ms
memory: 5492kb
input:
MMACQBRQABRC
output:
Bob
result:
ok single line: 'Bob'
Test #34:
score: 0
Accepted
time: 0ms
memory: 4228kb
input:
QACMQABRMCBR
output:
Alice
result:
ok single line: 'Alice'
Test #35:
score: 0
Accepted
time: 13ms
memory: 6196kb
input:
ACAQRCMRMBQB
output:
Alice
result:
ok single line: 'Alice'
Test #36:
score: 0
Accepted
time: 21ms
memory: 7648kb
input:
RABQCQMCABMR
output:
Bob
result:
ok single line: 'Bob'
Test #37:
score: 0
Accepted
time: 10ms
memory: 5676kb
input:
QQBARCRBMMAC
output:
Alice
result:
ok single line: 'Alice'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3916kb
input:
RQMRQABCABCM
output:
Alice
result:
ok single line: 'Alice'
Test #39:
score: 0
Accepted
time: 6ms
memory: 4680kb
input:
RQAMBRQCCBMA
output:
Alice
result:
ok single line: 'Alice'
Test #40:
score: 0
Accepted
time: 2ms
memory: 4084kb
input:
QQBACMARMRBC
output:
Alice
result:
ok single line: 'Alice'
Test #41:
score: 0
Accepted
time: 14ms
memory: 6368kb
input:
QAQCRRAMMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #42:
score: 0
Accepted
time: 11ms
memory: 5956kb
input:
QQBMCBRARMAC
output:
Bob
result:
ok single line: 'Bob'
Test #43:
score: 0
Accepted
time: 84ms
memory: 17776kb
input:
BABARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #44:
score: 0
Accepted
time: 487ms
memory: 63776kb
input:
BBARARCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #45:
score: 0
Accepted
time: 51ms
memory: 12064kb
input:
BBAARCRCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #46:
score: 0
Accepted
time: 141ms
memory: 26080kb
input:
BBAARRCQCQMM
output:
Bob
result:
ok single line: 'Bob'
Test #47:
score: 0
Accepted
time: 105ms
memory: 21356kb
input:
BBAARRCCQMQM
output:
Bob
result:
ok single line: 'Bob'
Test #48:
score: 0
Accepted
time: 318ms
memory: 51548kb
input:
BBAACCRQMQRM
output:
Bob
result:
ok single line: 'Bob'
Test #49:
score: 0
Accepted
time: 437ms
memory: 67512kb
input:
BACBACQRRQMM
output:
Bob
result:
ok single line: 'Bob'
Test #50:
score: 0
Accepted
time: 1171ms
memory: 139804kb
input:
RAABBRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #51:
score: 0
Accepted
time: 65ms
memory: 15224kb
input:
RABRBQMCACQM
output:
Bob
result:
ok single line: 'Bob'
Test #52:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
CMMQQABCRABR
output:
Alice
result:
ok single line: 'Alice'
Test #53:
score: 0
Accepted
time: 196ms
memory: 33360kb
input:
RBAABRCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Extra Test:
score: 0
Extra Test Passed