QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#314671#7635. Fairy ChessinksamuraiAC ✓1419ms139996kbC++233.1kb2024-01-26 03:16:232024-01-26 03:16:23

Judging History

你现在查看的是最新测评结果

  • [2024-01-26 03:16:23]
  • 评测
  • 测评结果:AC
  • 用时:1419ms
  • 内存:139996kb
  • [2024-01-26 03:16:23]
  • 提交

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