QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#231468#7635. Fairy Chessucup-team133AC ✓400ms3840kbC++233.3kb2023-10-29 12:34:572023-10-29 12:34:58

Judging History

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

  • [2023-10-29 12:34:58]
  • 评测
  • 测评结果:AC
  • 用时:400ms
  • 内存:3840kb
  • [2023-10-29 12:34:57]
  • 提交

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;
            if (self(self, cur | mass[c][i], koma | 1ULL << i, d + 1) == 0) return 1;
        }
        // return mp[d][{cur, koma}] = 0;
        return 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: 39ms
memory: 3840kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

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

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

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

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 53ms
memory: 3656kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

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

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 127ms
memory: 3608kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

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

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

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

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed