QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#594062#7635. Fairy Chessucup-team3519#AC ✓147ms3844kbC++174.1kb2024-09-27 18:40:562024-09-27 18:40:57

Judging History

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

  • [2024-09-27 18:40:57]
  • 评测
  • 测评结果:AC
  • 用时:147ms
  • 内存:3844kb
  • [2024-09-27 18:40:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define V vector
#define pb push_back

void apply_sig(ULL &bit, int x, int y) {
    if(x >= 0 && y >= 0 && x <= 7 && y <= 7) bit |= 1ULL << (x + y * 8);
}

void show(ULL x) {
    for(int i = 0; i < 8; i++) {
        for(int j = 0; j < 8; j++) {
            cout << (x >> (j * 8 + i) & 1);
        }
        cout << endl;
    }
}

ULL apply(ULL bit, int id, char c) {
    int x = id % 8, y = id / 8;
    // cout << "apply : " << c << " on : " << x << " " << y << endl;
    // show(bit);
    if(c == 'R' || c == 'Q' || c == 'M' || c == 'C') {//ju
        for(int i = 0; i < 8; i++) {
            apply_sig(bit, x, i);
            apply_sig(bit, i, y);
        }
    }
    if(c == 'Q' || c == 'M' || c == 'B' || c == 'A') {//xiang
        int n_x = x, n_y = y;
        while(n_x && n_y) n_x--, n_y--;
        while(n_x < 8 && n_y < 8) apply_sig(bit, n_x, n_y), n_x++, n_y++;

        n_x = x, n_y = y;
        while(n_x != 0 && n_y != 7) n_x--, n_y++;
        while(n_x < 8 && n_y >= 0) {
            apply_sig(bit, n_x, n_y), n_x++, n_y--;
        }
    }
    if(c == 'A' || c == 'C' || c == 'M') {
        apply_sig(bit, x - 2, y - 1);
        apply_sig(bit, x - 1, y - 2);
        apply_sig(bit, x - 2, y + 1);
        apply_sig(bit, x - 1, y + 2);
        apply_sig(bit, x + 2, y - 1);
        apply_sig(bit, x + 1, y - 2);
        apply_sig(bit, x + 2, y + 1);
        apply_sig(bit, x + 1, y + 2);
    }
    // cout << "output : " << bit << endl;
    // show(bit);
    // system("pause");
    return bit;
}

int main() {
    string s; cin >> s;
    map<pair<int, ULL>, bool> mp;

    V<V<ULL>> store(64, V<ULL>(26));
    for(int i = 0; i < 64; i++) {
        store[i]['A' - 'A'] = apply(0, i, 'A');
        store[i]['C' - 'A'] = apply(0, i, 'C');
        store[i]['M' - 'A'] = apply(0, i, 'M');
        store[i]['B' - 'A'] = apply(0, i, 'B');
        store[i]['R' - 'A'] = apply(0, i, 'R');
        store[i]['Q' - 'A'] = apply(0, i, 'Q');
        // if(i == 12) {
        //     cout << " i : " << i << endl;
        //     cout << " c : " << 'A' << endl;
        //     show(store[i]['A' - 'A']);
        //     cout << " i : " << i << endl;
        //     cout << " c : " << 'C' << endl;
        //     show(store[i]['C' - 'A']);
        //     cout << " i : " << i << endl;
        //     cout << " c : " << 'M' << endl;
        //     show(store[i]['M' - 'A']);
        //     cout << " i : " << i << endl;
        //     cout << " c : " << 'R' << endl;
        //     show(store[i]['R' - 'A']);
        //     cout << " i : " << i << endl;
        //     cout << " c : " << 'Q' << endl;
        //     show(store[i]['Q' - 'A']);
        //     cout << " i : " << i << endl;
        //     cout << " c : " << 'B' << endl;
        //     show(store[i]['B' - 'A']);
        // }

    }

    auto better_apply = [&](ULL board, int pos, char c) {
        ULL ans = board | store[pos][c - 'A'];
        // assert(ans == apply(board, pos, c));
        return ans;
    };

    auto id = [&](int x, int y) -> int {
        return y * 8 + x;
    };
    // int time = 0;
    auto dfs = [&](int pos, ULL board, ULL chess, auto dfs) -> bool {
        // time++;
        // if(time % 10000000 == 0) cout << time << endl;
        if(board == ~0ULL) return 0;
        assert(pos < 12);
        bool ok = 0;
        ULL find_board = ~board;
        while(find_board) {
            int i = __lg(find_board);
            find_board ^= 1ULL << i;
            assert(!(board >> i & 1));

            ULL n_board = better_apply(board, i, s[pos]);
            if(better_apply(0, i, s[pos]) & chess) continue;
            ULL n_chess = chess | (1ULL << i);

            if(!dfs(pos + 1, n_board, n_chess, dfs)) {
                ok = 1;
                break;
            }
            
        }
        // return mp[{pos, board}] = ok;
        return ok;
    };
    auto alice = dfs(0, 0, 0, dfs);
    cout << (alice ? "Alice" : "Bob") << endl;
}    

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 16ms
memory: 3764kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

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

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

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

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

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

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

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

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

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

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

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

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

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

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed