QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#231465#7635. Fairy Chessucup-team133AC ✓1319ms112368kbC++233.2kb2023-10-29 12:34:012023-10-29 12:34:02

Judging History

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

  • [2023-10-29 12:34:02]
  • 评测
  • 测评结果:AC
  • 用时:1319ms
  • 内存:112368kb
  • [2023-10-29 12:34:01]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

template <class T> istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}

template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
    auto sep = "";
    for (const auto& x : v) os << exchange(sep, " ") << x;
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

using ull = unsigned long long;
const int MAX = 8, PIECE = 6;

int f(int x, int y) { return x * MAX + y; }

int ctoi(char c) {
    if (c == 'B') return 0;
    if (c == 'R') return 1;
    if (c == 'Q') return 2;
    if (c == 'A') return 3;
    if (c == 'C') return 4;
    if (c == 'M') return 5;
    assert(false);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector mass(PIECE + 1, vector<ull>(MAX * MAX, 0));
    for (int x = 0; x < MAX; x++) {
        for (int y = 0; y < MAX; y++) {
            for (int nx = 0; nx < MAX; nx++) {
                for (int ny = 0; ny < MAX; ny++) {
                    if (x - y == nx - ny or x + y == nx + ny) mass[0][f(x, y)] |= 1ULL << f(nx, ny);
                    if (x == nx or y == ny) mass[1][f(x, y)] |= 1ULL << f(nx, ny);
                    if (x == nx and y == ny) mass[6][f(x, y)] |= 1ULL << f(nx, ny);
                    if (abs(x - nx) == 2 and abs(y - ny) == 1)
                        mass[6][f(x, y)] |= 1ULL << f(nx, ny);
                    else if (abs(x - nx) == 1 and abs(y - ny) == 2)
                        mass[6][f(x, y)] |= 1ULL << f(nx, ny);
                }
            }
            mass[2][f(x, y)] = mass[0][f(x, y)] | mass[1][f(x, y)];
            mass[3][f(x, y)] = mass[0][f(x, y)] | mass[6][f(x, y)];
            mass[4][f(x, y)] = mass[1][f(x, y)] | mass[6][f(x, y)];
            mass[5][f(x, y)] = mass[2][f(x, y)] | mass[6][f(x, y)];
        }
    }
    string S;
    cin >> S;
    int n = S.size();
    vector<map<pair<ull, ull>, int>> mp(n + 1);
    auto dfs = [&](auto self, ull cur, ull koma, int d) -> int {
        if (mp[d].count({cur, koma})) return mp[d][{cur, koma}];
        assert(d < n);
        int c = ctoi(S[d]);
        for (int i = 0; i < MAX * MAX; i++) {
            if (cur >> i & 1) continue;
            if (koma & mass[c][i]) continue;
            if (self(self, cur | mass[c][i], koma | 1ULL << i, d + 1) == 0) return mp[d][{cur, koma}] = 1;
        }
        return mp[d][{cur, koma}] = 0;
    };
    int ans = dfs(dfs, 0, 0, 0);
    cout << (ans ? "Alice" : "Bob") << "\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 120ms
memory: 17720kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

score: 0
Accepted
time: 47ms
memory: 9836kb

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 82ms
memory: 14256kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

score: 0
Accepted
time: 27ms
memory: 7864kb

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 92ms
memory: 14640kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 550ms
memory: 51504kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 152ms
memory: 21436kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 116ms
memory: 17588kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 376ms
memory: 41724kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 553ms
memory: 54528kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 1319ms
memory: 112368kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 226ms
memory: 27160kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed