QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#229055#7635. Fairy Chessucup-team987#AC ✓1265ms112288kbC++201.8kb2023-10-28 14:56:202023-10-28 14:56:22

Judging History

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

  • [2023-10-28 14:56:22]
  • 评测
  • 测评结果：AC
  • 用时：1265ms
  • 内存：112288kb
查看
  • [2023-10-28 14:56:20]
  • 提交

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<pair<ull,ull>,bool>memo[13];
bool win(int id,ull mp,ull pos)
{
	assert(id<12);
	if(!~mp)return false;
	if(memo[id].find(make_pair(mp,pos))!=memo[id].end())return memo[id][make_pair(mp,pos)];
	bool fn=false;
	for(int i=0;i<64;i++)if(!(mp>>i&1))
	{
		ull t=D[S[id]][i];
		if((pos&t)==0&&!win(id+1,mp|D[S[id]][i],pos|1uLL<<i))
		{
			fn=true;
			break;
		}
	}
	return memo[id][make_pair(mp,pos)]=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,0uLL)?"Alice":"Bob")<<endl;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 113ms
memory: 17636kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

score: 0
Accepted
time: 6ms
memory: 4516kb

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

score: 0
Accepted
time: 3ms
memory: 3980kb

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

score: 0
Accepted
time: 11ms
memory: 5404kb

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3932kb

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

score: 0
Accepted
time: 7ms
memory: 4708kb

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

score: 0
Accepted
time: 6ms
memory: 5400kb

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

score: 0
Accepted
time: 7ms
memory: 5152kb

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

score: 0
Accepted
time: 11ms
memory: 5276kb

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

score: 0
Accepted
time: 6ms
memory: 4440kb

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

score: 0
Accepted
time: 13ms
memory: 5984kb

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

score: 0
Accepted
time: 44ms
memory: 9556kb

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3732kb

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

score: 0
Accepted
time: 27ms
memory: 7828kb

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

score: 0
Accepted
time: 9ms
memory: 4624kb

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

score: 0
Accepted
time: 38ms
memory: 9316kb

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

score: 0
Accepted
time: 40ms
memory: 9912kb

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3744kb

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

score: 0
Accepted
time: 23ms
memory: 7104kb

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

score: 0
Accepted
time: 5ms
memory: 4264kb

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 76ms
memory: 14268kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

score: 0
Accepted
time: 22ms
memory: 7416kb

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

score: 0
Accepted
time: 19ms
memory: 7328kb

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

score: 0
Accepted
time: 14ms
memory: 5780kb

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

score: 0
Accepted
time: 2ms
memory: 3740kb

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

score: 0
Accepted
time: 18ms
memory: 6240kb

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

score: 0
Accepted
time: 6ms
memory: 4640kb

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

score: 0
Accepted
time: 35ms
memory: 9252kb

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

score: 0
Accepted
time: 7ms
memory: 5404kb

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

score: 0
Accepted
time: 2ms
memory: 3880kb

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

score: 0
Accepted
time: 13ms
memory: 5832kb

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

score: 0
Accepted
time: 8ms
memory: 4856kb

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

score: 0
Accepted
time: 3ms
memory: 3896kb

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

score: 0
Accepted
time: 12ms
memory: 5596kb

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

score: 0
Accepted
time: 16ms
memory: 6736kb

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

score: 0
Accepted
time: 6ms
memory: 5008kb

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

score: 0
Accepted
time: 4ms
memory: 4192kb

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

score: 0
Accepted
time: 2ms
memory: 3800kb

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

score: 0
Accepted
time: 13ms
memory: 5748kb

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

score: 0
Accepted
time: 10ms
memory: 5340kb

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 89ms
memory: 14672kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 564ms
memory: 51624kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

score: 0
Accepted
time: 52ms
memory: 10188kb

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 141ms
memory: 21556kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 123ms
memory: 17756kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 391ms
memory: 41736kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 531ms
memory: 54448kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 1265ms
memory: 112288kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

score: 0
Accepted
time: 60ms
memory: 12500kb

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

score: 0
Accepted
time: 1ms
memory: 3508kb

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 216ms
memory: 27152kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-03 04:30:29 | OpenSource Project