QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226966#7635. Fairy ChessPhantomThreshold#AC ✓1171ms139804kbC++202.5kb2023-10-26 19:14:352023-10-26 19:14:35

Judging History

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

  • [2023-10-26 19:14:35]
  • 评测
  • 测评结果:AC
  • 用时:1171ms
  • 内存:139804kb
  • [2023-10-26 19:14:35]
  • 提交

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;	
}

Details

Tip: Click on the bar to expand more detailed information

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