QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#314671 | #7635. Fairy Chess | inksamurai | AC ✓ | 1419ms | 139996kb | C++23 | 3.1kb | 2024-01-26 03:16:23 | 2024-01-26 03:16:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _48SMghu ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
using ull=unsigned long long;
void slv(){
int n=8;
auto ok=[&](int i,int j){
return min(i,j)>=0 and max(i,j)<n;
};
auto id=[&](int i,int j){
return i*n+j;
};
auto piece=[&](char ch){
int ret=0;
if(ch=='R'){
ret=1;
}else if(ch=='B'){
ret=2;
}else if(ch=='Q'){
ret=3;
}else if(ch=='A'){
ret=4;
}else if(ch=='M'){
ret=5;
}else if(ch=='C'){
ret=6;
}
return ret;
};
vec(vec(ull)) graf(7,vec(ull)(64));
// K
{
const int di[]={-2,-2,-1,-1,2,2,1,1};
const int dj[]={1,-1,2,-2,1,-1,2,-2};
rep(i,n){
rep(j,n){
ull msk=0;
rep(dir,8){
int ni=i+di[dir],nj=j+dj[dir];
if(ok(ni,nj)){
msk|=(1ull<<id(ni,nj));
}
}
msk|=(1ull<<id(i,j));
graf[0][id(i,j)]=msk;
}
}
}
// R
{
rep(i,n){
rep(j,n){
ull msk=0;
rep(j1,n){
msk|=(1ull<<id(i,j1));
}
rep(i1,n){
msk|=(1ull<<id(i1,j));
}
graf[1][id(i,j)]=msk;
}
}
}
// B
{
rep(i,n){
rep(j,n){
ull msk=0;
rep(i1,n){
rep(j1,n){
if(i1-j1==i-j or i1+j1==i+j){
msk|=(1ull<<id(i1,j1));
}
}
}
graf[2][id(i,j)]=msk;
}
}
}
// Q
{
rep(i,n){
rep(j,n){
graf[3][id(i,j)]=graf[1][id(i,j)]|graf[2][id(i,j)];
}
}
}
// A
{
rep(i,n){
rep(j,n){
graf[4][id(i,j)]=graf[2][id(i,j)]|graf[0][id(i,j)];
}
}
}
// M
{
rep(i,n){
rep(j,n){
graf[5][id(i,j)]=graf[0][id(i,j)]|graf[3][id(i,j)];
}
}
}
// C
{
rep(i,n){
rep(j,n){
graf[6][id(i,j)]=graf[1][id(i,j)]|graf[0][id(i,j)];
}
}
}
string s;
cin>>s;
// rep(i,n){
// rep(j,n){
// if(graf[2][n+2]>>id(i,j)&1){
// cout<<"1";
// }else{
// cout<<"0";
// }
// }
// print();
// }
map<array<ull,3>,int> mp;
auto rec=[&](auto self,int i,ull placed,ull attacked)->int{
if(i==sz(s)){
return 0;
}
// if(i<3){
// print("go");
// }
// else{
// // print(i,__builtin_popcountll(attacked));
// return 0;
// }
if(mp.find({(ull)i,placed,attacked})!=mp.end()){
return mp[{(ull)i,placed,attacked}];
}
int id=piece(s[i]);
int ret=0;
rep(v,64){
if(attacked&(1ull<<v)) continue;
if(graf[id][v]&placed) continue;
if(not self(self,i+1,placed|(1ull<<v),attacked|graf[id][v])){
ret=1;
break;
}
}
return mp[{(ull)i,placed,attacked}]=ret;
};
if(rec(rec,0,0,0)){
cout<<"Alice\n";
}else{
cout<<"Bob\n";
}
}
signed main(){
_48SMghu;
slv();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 139ms
memory: 21284kb
input:
BBAARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 7ms
memory: 5188kb
input:
BAMBAMQQRCCR
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: 0
Accepted
time: 4ms
memory: 4204kb
input:
QQRAACMRMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #4:
score: 0
Accepted
time: 14ms
memory: 6224kb
input:
MBBARQRMACQC
output:
Alice
result:
ok single line: 'Alice'
Test #5:
score: 0
Accepted
time: 4ms
memory: 4288kb
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: 15ms
memory: 6100kb
input:
BBRCMMQAAQRC
output:
Alice
result:
ok single line: 'Alice'
Test #8:
score: 0
Accepted
time: 10ms
memory: 5976kb
input:
RRMCQMACABQB
output:
Alice
result:
ok single line: 'Alice'
Test #9:
score: 0
Accepted
time: 14ms
memory: 6104kb
input:
QMQBMRBACACR
output:
Alice
result:
ok single line: 'Alice'
Test #10:
score: 0
Accepted
time: 7ms
memory: 4996kb
input:
CMRQAQCBBRAM
output:
Alice
result:
ok single line: 'Alice'
Test #11:
score: 0
Accepted
time: 15ms
memory: 6800kb
input:
CABCRQMMRQAB
output:
Alice
result:
ok single line: 'Alice'
Test #12:
score: 0
Accepted
time: 52ms
memory: 11520kb
input:
ARCBBCMQRAQM
output:
Alice
result:
ok single line: 'Alice'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
ARCMCARMQBBQ
output:
Alice
result:
ok single line: 'Alice'
Test #14:
score: 0
Accepted
time: 32ms
memory: 9020kb
input:
AQABMCQCMRRB
output:
Bob
result:
ok single line: 'Bob'
Test #15:
score: 0
Accepted
time: 8ms
memory: 5220kb
input:
ACMRABRQMCBQ
output:
Alice
result:
ok single line: 'Alice'
Test #16:
score: 0
Accepted
time: 47ms
memory: 10648kb
input:
CBARMBCQMQAR
output:
Bob
result:
ok single line: 'Bob'
Test #17:
score: 0
Accepted
time: 54ms
memory: 11516kb
input:
RBABRQMCAMQC
output:
Bob
result:
ok single line: 'Bob'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3920kb
input:
MBCQBQARRMCA
output:
Alice
result:
ok single line: 'Alice'
Test #19:
score: 0
Accepted
time: 25ms
memory: 8156kb
input:
AMBQRBCQACMR
output:
Bob
result:
ok single line: 'Bob'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
QRAMQMBBCRAC
output:
Alice
result:
ok single line: 'Alice'
Test #21:
score: 0
Accepted
time: 5ms
memory: 4800kb
input:
ARBCQMMBARQC
output:
Alice
result:
ok single line: 'Alice'
Test #22:
score: 0
Accepted
time: 96ms
memory: 17096kb
input:
CACAMBRQQRBM
output:
Bob
result:
ok single line: 'Bob'
Test #23:
score: 0
Accepted
time: 35ms
memory: 9080kb
input:
CQRRMMBQABCA
output:
Bob
result:
ok single line: 'Bob'
Test #24:
score: 0
Accepted
time: 25ms
memory: 8248kb
input:
ABABCQRMMCRQ
output:
Alice
result:
ok single line: 'Alice'
Test #25:
score: 0
Accepted
time: 17ms
memory: 6540kb
input:
CMBRAAQRQMBC
output:
Bob
result:
ok single line: 'Bob'
Test #26:
score: 0
Accepted
time: 2ms
memory: 4132kb
input:
AQBMRMQRBACC
output:
Alice
result:
ok single line: 'Alice'
Test #27:
score: 0
Accepted
time: 19ms
memory: 7464kb
input:
BRACQQMCAMBR
output:
Bob
result:
ok single line: 'Bob'
Test #28:
score: 0
Accepted
time: 7ms
memory: 4836kb
input:
MCCAQBMQRABR
output:
Bob
result:
ok single line: 'Bob'
Test #29:
score: 0
Accepted
time: 40ms
memory: 10808kb
input:
RBQBCRAACMQM
output:
Bob
result:
ok single line: 'Bob'
Test #30:
score: 0
Accepted
time: 14ms
memory: 6100kb
input:
ACRQARMBBQMC
output:
Bob
result:
ok single line: 'Bob'
Test #31:
score: 0
Accepted
time: 2ms
memory: 3956kb
input:
MRCQBCBQRMAA
output:
Alice
result:
ok single line: 'Alice'
Test #32:
score: 0
Accepted
time: 16ms
memory: 6416kb
input:
ACRQQCMMBBAR
output:
Bob
result:
ok single line: 'Bob'
Test #33:
score: 0
Accepted
time: 9ms
memory: 5652kb
input:
MMACQBRQABRC
output:
Bob
result:
ok single line: 'Bob'
Test #34:
score: 0
Accepted
time: 3ms
memory: 4196kb
input:
QACMQABRMCBR
output:
Alice
result:
ok single line: 'Alice'
Test #35:
score: 0
Accepted
time: 14ms
memory: 6140kb
input:
ACAQRCMRMBQB
output:
Alice
result:
ok single line: 'Alice'
Test #36:
score: 0
Accepted
time: 17ms
memory: 7504kb
input:
RABQCQMCABMR
output:
Bob
result:
ok single line: 'Bob'
Test #37:
score: 0
Accepted
time: 11ms
memory: 5820kb
input:
QQBARCRBMMAC
output:
Alice
result:
ok single line: 'Alice'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
RQMRQABCABCM
output:
Alice
result:
ok single line: 'Alice'
Test #39:
score: 0
Accepted
time: 2ms
memory: 4588kb
input:
RQAMBRQCCBMA
output:
Alice
result:
ok single line: 'Alice'
Test #40:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
QQBACMARMRBC
output:
Alice
result:
ok single line: 'Alice'
Test #41:
score: 0
Accepted
time: 15ms
memory: 6308kb
input:
QAQCRRAMMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #42:
score: 0
Accepted
time: 9ms
memory: 5860kb
input:
QQBMCBRARMAC
output:
Bob
result:
ok single line: 'Bob'
Test #43:
score: 0
Accepted
time: 100ms
memory: 17640kb
input:
BABARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #44:
score: 0
Accepted
time: 648ms
memory: 63636kb
input:
BBARARCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #45:
score: 0
Accepted
time: 53ms
memory: 12000kb
input:
BBAARCRCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #46:
score: 0
Accepted
time: 182ms
memory: 26036kb
input:
BBAARRCQCQMM
output:
Bob
result:
ok single line: 'Bob'
Test #47:
score: 0
Accepted
time: 135ms
memory: 21340kb
input:
BBAARRCCQMQM
output:
Bob
result:
ok single line: 'Bob'
Test #48:
score: 0
Accepted
time: 400ms
memory: 51448kb
input:
BBAACCRQMQRM
output:
Bob
result:
ok single line: 'Bob'
Test #49:
score: 0
Accepted
time: 513ms
memory: 67680kb
input:
BACBACQRRQMM
output:
Bob
result:
ok single line: 'Bob'
Test #50:
score: 0
Accepted
time: 1419ms
memory: 139996kb
input:
RAABBRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #51:
score: 0
Accepted
time: 71ms
memory: 15036kb
input:
RABRBQMCACQM
output:
Bob
result:
ok single line: 'Bob'
Test #52:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
CMMQQABCRABR
output:
Alice
result:
ok single line: 'Alice'
Test #53:
score: 0
Accepted
time: 260ms
memory: 33176kb
input:
RBAABRCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Extra Test:
score: 0
Extra Test Passed