QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#230921#7635. Fairy Chessucup-team1951#AC ✓663ms3480kbC++203.3kb2023-10-28 22:03:572023-10-28 22:03:58

Judging History

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

  • [2023-10-28 22:03:58]
  • 评测
  • 测评结果：AC
  • 用时：663ms
  • 内存：3480kb
查看
  • [2023-10-28 22:03:57]
  • 提交

answer

#include <algorithm>
#include <iostream>
#include <vector>


using ll = long long;
using ull = unsigned long long;

ull bishop(int i, int j) {
    ull res = 0;
    for (int k = -7; k < 8; k++) {
        if (i + k >= 0 && i + k < 8 && j + k >= 0 && j + k < 8) {
            res |= (1ULL << ((i + k) * 8 + j + k));
        }
        if (i + k >= 0 && i + k < 8 && j - k >= 0 && j - k < 8) {
            res |= (1ULL << ((i + k) * 8 + j - k));
        }
    }
    return res;
}

ull rock(int i, int j) {
    ull res = 0;
    for (int k = 0; k < 8; k++) {
        res |= (1ULL << (i * 8 + k));
        res |= (1ULL << (k * 8 + j));
    }
    return res;
}

ull queen(int i, int j) {
    ull res = rock(i, j) | bishop(i, j);
    constexpr std::pair<int, int> moves[] = {
        {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
    for (auto [di, dj] : moves) {
        int ii = i + di;
        int jj = j + dj;
        if (ii >= 0 && ii < 8 && jj >= 0 && jj < 8) {
            res |= (1ULL << (ii * 8 + jj));
        }
    }
    return res;
}

ull knight(int i, int j) {
    ull res = 0;
    constexpr std::pair<int, int> moves[] = {
        {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};
    for (auto [di, dj] : moves) {
        int ii = i + di;
        int jj = j + dj;
        if (ii >= 0 && ii < 8 && jj >= 0 && jj < 8) {
            res |= (1ULL << (ii * 8 + jj));
        }
    }
    return res;
}

ull archbishop(int i, int j) {
    ull res = bishop(i, j) | knight(i, j);
    return res;
}

ull chancellor(int i, int j) {
    ull res = rock(i, j) | knight(i, j);
    return res;
}

ull maharaja(int i, int j) {
    ull res = queen(i, j) | knight(i, j);
    return res;
}

using state = std::pair<ull, ull>;

std::string order;

bool search(int turn, state s) {
    if (turn == order.size()) {
        return false;
    }

    char c = order[turn];

    bool result = false;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (s.first & (1ULL << (i * 8 + j))) {
                continue;
            }
            ull move;
            switch (c) {
            case 'B':
                move = bishop(i, j);
                break;
            case 'R':
                move = rock(i, j);
                break;
            case 'Q':
                move = queen(i, j);
                break;
            case 'N':
                move = knight(i, j);
                break;
            case 'A':
                move = archbishop(i, j);
                break;
            case 'C':
                move = chancellor(i, j);
                break;
            case 'M':
                move = maharaja(i, j);
                break;
            }

            if (s.second & move) {
                continue;
            }

            result |= !search(
                turn + 1, {s.first | move, s.second | (1ULL << (i * 8 + j))});

            if (result) {
                break;
            }
        }
        if (result) {
            break;
        }
    }

    return result;
}

int main() {
    std::string s;
    std::cin >> s;

    order = s;

    bool result = search(0, {0, 0});

    std::cout << (result ? "Alice" : "Bob") << std::endl;

    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 65ms
memory: 3420kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 50ms
memory: 3376kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 400ms
memory: 3384kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

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

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 254ms
memory: 3360kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 250ms
memory: 3364kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 663ms
memory: 3476kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 125ms
memory: 3368kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

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

Server Time: 2024-12-03 00:46:11 | OpenSource Project