QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#245174#7635. Fairy Chessucup-team2307#AC ✓645ms41396kbC++173.4kb2023-11-09 19:35:402023-11-09 19:35:43

Judging History

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

  • [2023-11-09 19:35:43]
  • 评测
  • 测评结果:AC
  • 用时:645ms
  • 内存:41396kb
  • [2023-11-09 19:35:40]
  • 提交

answer

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second

using namespace std;

typedef unsigned long long ull;
vector<pair<int, int> > knight = { {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1} };

bool ok(int i)
{
    return (i >= 0 && i < 8);
}
bool ok(int i, int j)
{
    return (i >= 0 && i < 8 && j >= 0 && j < 8);
}
int id(int i, int j)
{
    return 8*i+j;
}

ull Move(ull bef, char c, int x, int y)
{
    bef |= ull(1) << id(x, y);
    if (c == 'A' || c == 'C' || c == 'M')
    {
        for (auto [i, j] : knight)
            if (ok(x+i, y+j))
                bef |= ull(1) << id(x+i, y+j);
    }
    if (c == 'B' || c == 'A' || c == 'Q' || c == 'M')
    {
        for (int i=0; i<8; i++)
        {
            if (ok(x+y-i))
                bef |= ull(1) << id(i, x+y-i);
            if (ok(-x+y+i))
                bef |= ull(1) << id(i,-x+y+i);
        }
    }
    if (c == 'R' || c == 'C' || c == 'Q' || c == 'M')
    {
        for (int i=0; i<8; i++)
        {
            bef |= ull(1) << id(i, y);
            bef |= ull(1) << id(x, i);
        }
    }
    return bef;
}
bool CanPlace(ull bef, char c, int x, int y)
{
    if (bef & (ull(1) << id(x, y)))
        return false;
    if (c == 'A' || c == 'C' || c == 'M')
    {
        for (auto [i, j] : knight)
            if (ok(x+i, y+j))
                if (bef & (ull(1) << id(x+i, y+j)))
                    return false;
    }
    if (c == 'B' || c == 'A' || c == 'Q' || c == 'M')
    {
        for (int i=0; i<8; i++)
        {
            if (ok(x+y-i))
                if (bef & (ull(1) << id(i, x+y-i)))
                    return false;
            if (ok(-x+y+i))
                if (bef & (ull(1) << id(i,-x+y+i)))
                    return false;
        }
    }
    if (c == 'R' || c == 'C' || c == 'Q' || c == 'M')
    {
        for (int i=0; i<8; i++)
        {
            if (bef & (ull(1) << id(i, y)))
                return false;
            if (bef & (ull(1) << id(x, i)))
                return false;
        }
    }
    return true;
}

int cnt(ull brd)
{
    return __builtin_popcountll(brd);
}

string s;
map<pair<ull, ull>, bool> mp[20];

void out(ull brd)
{
    for (int x=0; x<8; x++, cout<<endl)
        for (int y=0; y<8; y++)
            cout<<((brd>>id(x, y))&1);
    cout<<endl;
}

bool win(ull brd, ull figs, int i)
{
    if (i == 12)
        return 0;
    if (cnt(brd) == 64)
        return false;
    if (mp[i].count({brd, figs}))
        return mp[i][{brd, figs}];

    vector<pair<ull, ull> > brds;
    for (int x=0; x<8; x++)
        for (int y=0; y<8; y++)
            if (((brd>>id(x, y)) & ull(1)) == 0)
                if (CanPlace(figs, s[i], x, y))
                    brds.pb({Move(brd, s[i], x, y), figs | (ull(1) << id(x, y))});
    sort(brds.begin(), brds.end(), [](pair<ull, ull> x, pair<ull, ull> y){ return cnt(x.fi) > cnt(y.fi); });

    bool ok = false;
    for (auto b : brds)
        if (!win(b.fi, b.se, i+1))
    {
        ok = true;
        break;
    }

//    cout<<ok<<" "<<i<<" "<<s[i]<<"\n";
//    out(brd);

    return mp[i][{brd, figs}] = ok;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen("out.txt", "w", stdout);

    cin>>s;
    if (win(0, 0, 0))
        cout<<"Alice\n";
    else
        cout<<"Bob\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 35ms
memory: 6724kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

score: 0
Accepted
time: 39ms
memory: 7252kb

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

score: 0
Accepted
time: 165ms
memory: 17180kb

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

score: 0
Accepted
time: 15ms
memory: 4892kb

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

score: 0
Accepted
time: 48ms
memory: 6852kb

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

score: 0
Accepted
time: 28ms
memory: 5812kb

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

score: 0
Accepted
time: 15ms
memory: 5044kb

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

score: 0
Accepted
time: 37ms
memory: 6216kb

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

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

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

score: 0
Accepted
time: 196ms
memory: 17008kb

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

score: 0
Accepted
time: 21ms
memory: 4984kb

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

score: 0
Accepted
time: 24ms
memory: 6152kb

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

score: 0
Accepted
time: 30ms
memory: 5868kb

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

score: 0
Accepted
time: 26ms
memory: 5936kb

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 31ms
memory: 6072kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

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

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 36ms
memory: 7008kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 30ms
memory: 6700kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 184ms
memory: 15524kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 645ms
memory: 41396kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 529ms
memory: 41140kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

score: 0
Accepted
time: 177ms
memory: 16168kb

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 25ms
memory: 5752kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed