QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#298782#7635. Fairy Chessucup-team1525#AC ✓68ms3816kbC++172.1kb2024-01-06 14:44:402024-01-06 14:44:40

Judging History

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

  • [2024-01-06 14:44:40]
  • 评测
  • 测评结果:AC
  • 用时:68ms
  • 内存:3816kb
  • [2024-01-06 14:44:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long 
const int X[8]={1,1,2,2,-1,-1,-2,-2};
const int Y[8]={2,-2,1,-1,2,-2,1,-1};
int mp[100];
ull f[6][64];
char s[100];
int a[100];
const int in[]={0,1,2,3,9,10,11,18,19,27};
ull mi(int x)
{
    return 1ULL<<x;
}
int dfs(int x,ull y,ull z)
{
    if (x==12)
        return 0;
    if (__builtin_popcountll(y)==64)
        return x&1;
    if (x&1)
    {   
        for (int i=0;i<64;++i)
            if (((y>>i)&1)==0&&((z&f[a[x]][i])==0))
                if (dfs(x+1,y|f[a[x]][i],z|mi(i))==0)
                    return 0;
        return 1;
    }
    else
    {
        if (x!=0)
        {
            for (int i=0;i<64;++i)
                 if (((y>>i)&1)==0&&((z&f[a[x]][i])==0))
                    if (dfs(x+1,y|f[a[x]][i],z|mi(i))==1)
                        return 1;
        }
        else
        {
            for (int i:in)
                 if (((y>>i)&1)==0&&((z&f[a[x]][i])==0))
                    if (dfs(x+1,y|f[a[x]][i],z|mi(i))==1)
                        return 1;
        }
        return 0;
    }
}
int main()
{
    mp['B']=0;
    mp['R']=1;
    mp['Q']=2;
    mp['A']=3;
    mp['C']=4;
    mp['M']=5;
    for (int i=0;i<8;++i)
        for (int j=0;j<8;++j)
        {
            int p=i*8+j;
            for (int x=0;x<8;++x)
                for (int y=0;y<8;++y)
                {
                    int q=x*8+y;
                    if (x==i||y==j)
                        f[1][p]|=mi(q);
                    if (abs(x-i)==abs(y-j))
                        f[0][p]|=mi(q);
                }
            f[2][p]=f[0][p]|f[1][p];
            ull tmp=0;
            for (int k=0;k<8;++k)
            {
                int _x=i+X[k];
                int _y=j+Y[k];
                if (_x>=0&&_x<8&&_y>=0&&_y<8)
                    tmp|=mi(_x*8+_y);
            }
            for (int k=0;k<3;++k)
                f[k+3][p]=f[k][p]|tmp;
        }
    scanf("%s",s);
    for (int i=0;i<12;++i)
        a[i]=mp[s[i]];
    if (dfs(0,0,0))
        cout<<"Alice";
    else
        cout<<"Bob";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 3580kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

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

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 68ms
memory: 3720kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

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

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 17ms
memory: 3552kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

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

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 41ms
memory: 3796kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

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

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed