QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#230439#7635. Fairy Chessucup-team228#AC ✓1711ms3864kbC++205.7kb2023-10-28 18:40:032023-10-28 18:40:03

Judging History

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

  • [2023-10-28 18:40:03]
  • 评测
  • 测评结果:AC
  • 用时:1711ms
  • 内存:3864kb
  • [2023-10-28 18:40:03]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int n = 8;

vector<pair<int, int>> get_bishop() {
    vector<pair<int, int>> res;
    for (int i = 1; i <= n - 1; i++) {
        res.emplace_back(i, i);
        res.emplace_back(-i, i);
        res.emplace_back(i, -i);
        res.emplace_back(-i, -i);
    }
    return res;
}

vector<pair<int, int>> get_rook() {
    vector<pair<int, int>> res;
    for (int i = 1; i <= n - 1; i++) {
        res.emplace_back(i, 0);
        res.emplace_back(-i, 0);
        res.emplace_back(0, i);
        res.emplace_back(0, -i);
    }
    return res;
}

vector<pair<int, int>> get_queen() {
    vector<pair<int, int>> res;
    auto rook = get_rook();
    auto bishop = get_bishop();
    for (auto d : rook) {
        res.push_back(d);
    }
    for (auto d : bishop) {
        res.push_back(d);
    }
    return res;
}

vector<pair<int, int>> get_knight() {
    vector<pair<int, int>> res;
    for (int i = -2; i <= 2; i++) {
        for (int j = -2; j <= 2; j++) {
            if (i != 0 && j != 0 && abs(i) != abs(j)) {
                res.emplace_back(i, j);
            }
        }
    }
    return res;
}

vector<pair<int, int>> get_archibishop() {
    vector<pair<int, int>> res;
    auto bishop = get_bishop();
    auto knight = get_knight();
    for (auto d : bishop) {
        res.push_back(d);
    }
    for (auto d : knight) {
        res.push_back(d);
    }
    return res;
}

vector<pair<int, int>> get_chancellor() {
    vector<pair<int, int>> res;
    auto rook = get_rook();
    auto knight = get_knight();
    for (auto d : rook) {
        res.push_back(d);
    }
    for (auto d : knight) {
        res.push_back(d);
    }
    return res;
}

vector<pair<int, int>> get_maharaja() {
    vector<pair<int, int>> res;
    auto queen = get_queen();
    auto knight = get_knight();
    for (auto d : queen) {
        res.push_back(d);
    }
    for (auto d : knight) {
        res.push_back(d);
    }
    return res;
}

vector<pair<int, int>> db = get_bishop();
vector<pair<int, int>> dr = get_rook();
vector<pair<int, int>> dq = get_queen();
vector<pair<int, int>> da = get_archibishop();
vector<pair<int, int>> dc = get_chancellor();
vector<pair<int, int>> dm = get_maharaja();

bool used[n + 2][n + 2];
int cnt[n + 2][n + 2];

bool solve(int idx, const string& s) {
    if (idx == s.size()) {
        return false;
    } else {
        bool ans = false;
        vector<pair<int, int>>* dcur = &db;
        if (s[idx] == 'B') {
            dcur = &db;
        } else if (s[idx] == 'R') {
            dcur = &dr;
        } else if (s[idx] == 'Q') {
            dcur = &dq;
        } else if (s[idx] == 'A') {
            dcur = &da;
        } else if (s[idx] == 'C') {
            dcur = &dc;
        } else if (s[idx] == 'M') {
            dcur = &dm;
        } else {
            assert(false);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (!used[i][j] && cnt[i][j] == 0) {
                    bool ok = true;
                    for (auto [di, dj] : *dcur) {
                        if (1 <= i + di && i + di <= n && 1 <= j + dj && j + dj <= n) {
                            if (used[i + di][j + dj]) {
                                ok = false;
                            }
                        }
                    }
                    if (ok) {
                        used[i][j] = true;
                        for (auto [di, dj] : *dcur) {
                            if (1 <= i + di && i + di <= n && 1 <= j + dj && j + dj <= n) {
                                cnt[i + di][j + dj]++;
                            }
                        }
                        ans |= !solve(idx + 1, s);
                        used[i][j] = false;
                        for (auto [di, dj] : *dcur) {
                            if (1 <= i + di && i + di <= n && 1 <= j + dj && j + dj <= n) {
                                cnt[i + di][j + dj]--;
                            }
                        }
                        if (ans) {
                            return true;
                        }
                    }
                }
            }
        }
        return ans;
    }
}

void foo() {
    char a[n + 2][n + 2];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = '.';
        }
    }
    int x = 3, y = 4;
    a[x][y] = '*';
    for (auto [dx, dy] : dm) {
        if (1 <= x + dx && x + dx <= n && 1 <= y + dy && y + dy <= n) {
            a[x + dx][y + dy] = 'x';
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << a[i][j];
        }
        cout << "\n";
    }
    exit(0);
}

void stress_time() {
    mt19937 rnd;
    string s = "BBAARRCCQQMM";
    while (true) {
        shuffle(s.begin(), s.end(), rnd);
        cout << s << endl;
        if (solve(0, s)) {
            cout << "Alice" << endl;
        } else {
            cout << "Bob" << endl;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                assert(used[i][j] == false);
                assert(cnt[i][j] == 0);
            }
        }
    }
    exit(0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    // foo();
    // stress_time();

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

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 167ms
memory: 3768kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

score: 0
Accepted
time: 79ms
memory: 3844kb

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

score: 0
Accepted
time: 29ms
memory: 3616kb

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 115ms
memory: 3848kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

score: 0
Accepted
time: 32ms
memory: 3616kb

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 221ms
memory: 3848kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 1021ms
memory: 3504kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

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

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 622ms
memory: 3828kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 606ms
memory: 3764kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 1711ms
memory: 3504kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

score: 0
Accepted
time: 143ms
memory: 3616kb

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

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

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed