QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#228675#7635. Fairy Chessucup-team1198#AC ✓507ms3540kbC++202.8kb2023-10-28 13:57:102023-10-28 13:57:10

Judging History

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

  • [2023-10-28 13:57:10]
  • 评测
  • 测评结果:AC
  • 用时:507ms
  • 内存:3540kb
  • [2023-10-28 13:57:10]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

vector<int> moves;

int knight_steps_x[8] = {-2, -2, -1, 1, 2, 2, 1, -1};
int knight_steps_y[8] = {1, -1, -2, -2, -1, 1, 2, 2};

// 0: Bishop, 1: Rook, 2: Queen, 3: Archbishop, 4: Chancellor, 5: Maharaja

const unsigned long long ONE = 1ULL;
unsigned long long beats[6][64];


bool wins(int i, unsigned long long beated, unsigned long long figures) {
    if (i == moves.size())
        return false;
    int figure = moves[i];
    for (unsigned long long pos = 0; pos < 64; ++pos) {
        if (beated & (ONE << pos))
            continue;
        if (figures & beats[figure][pos])
            continue;
        bool res = wins(i + 1, beated | beats[figure][pos], figures | (ONE << pos));
        if (!res)
            return true;
    }
    return false;
}

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

    for (int x = 0; x < 8; ++x) {
        for (int y = 0; y < 8; ++y) {
            unsigned long long bishop_mask = 0ULL;
            unsigned long long rook_mask = 0ULL;
            unsigned long long knight_mask = 0ULL;

            for (int i = -7; i <= 7; ++i) {
                if (x + i >= 0 && x + i < 8 && y + i >= 0 && y + i < 8)
                    bishop_mask |= (ONE << (unsigned long long)((x + i) * 8 + (y + i)));
            }
            for (int i = -7; i <= 7; ++i) {
                if (x + i >= 0 && x + i < 8 && y - i >= 0 && y - i < 8)
                    bishop_mask |= (ONE << (unsigned long long)((x + i) * 8 + (y - i)));
            }
            for (int i = 0; i < 8; ++i)
                rook_mask |= (ONE << (unsigned long long)(i * 8 + y));
            for (int i = 0; i < 8; ++i)
                rook_mask |= (ONE << (unsigned long long)(x * 8 + i));
            for (int step = 0; step < 8; ++step) {
                int new_x = x + knight_steps_x[step];
                int new_y = y + knight_steps_y[step];
                if (new_x >= 0 && new_x < 8 && new_y >= 0 && new_y < 8)
                    knight_mask |= (ONE << (unsigned long long)(new_x * 8 + new_y));
            }
            beats[0][x * 8 + y] = bishop_mask;
            beats[1][x * 8 + y] = rook_mask;
            beats[2][x * 8 + y] = bishop_mask | rook_mask;
            beats[3][x * 8 + y] = bishop_mask | knight_mask;
            beats[4][x * 8 + y] = rook_mask | knight_mask;
            beats[5][x * 8 + y] = bishop_mask | rook_mask | knight_mask;
        }
    }
    string s;
    cin >> s;
    map<char, int> id;
    id['B'] = 0;
    id['R'] = 1;
    id['Q'] = 2;
    id['A'] = 3;
    id['C'] = 4;
    id['M'] = 5;
    for (char c : s) {
        moves.emplace_back(id[c]);
    }
    if (wins(0, 0ull, 0ull))
        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: 48ms
memory: 3396kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

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

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 59ms
memory: 3408kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

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

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 77ms
memory: 3412kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

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

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

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

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 507ms
memory: 3420kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 96ms
memory: 3424kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed