QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#250550#7635. Fairy ChessKKT89AC ✓1420ms163308kbC++173.5kb2023-11-13 12:27:032023-11-13 12:27:03

Judging History

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

  • [2023-11-13 12:27:03]
  • 评测
  • 测评结果:AC
  • 用时:1420ms
  • 内存:163308kb
  • [2023-11-13 12:27:03]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

ull bit(int x) {
    return ((ull)1 << x);
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    auto cid = [&](int x, int y) -> int {
        return x*8+y;
    };

    vector<ull> hi(64),ka(64),ke(64);
    vector<ull> ihi(64),ika(64),ike(64);
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            int id = cid(i,j);

            for (int k = 0; k < 8; ++k) {
                for (int l = 0; l < 8; ++l) {
                    int nid = cid(k,l);
                    if (k == i or j == l) {
                        hi[id] |= bit(nid);
                        ihi[nid] |= bit(id);
                    }
                    if (i+j == k+l or i-j == k-l) {
                        ka[id] |= bit(nid);
                        ika[nid] |= bit(id);
                    }
                    if (abs(k-i) == 1 and abs(j-l) == 2) {
                        ke[id] |= bit(nid);
                        ike[nid] |= bit(id);
                    }
                    if (abs(k-i) == 2 and abs(j-l) == 1) {
                        ke[id] |= bit(nid);
                        ike[nid] |= bit(id);
                    }
                }
            }
        }
    }

    ull kouho = 0;
    for (int i = 0; i < 64; ++i) {
        kouho |= bit(i);
    }

    string str = "BBAARRCCQQMM";
    cin >> str;
    map<tuple<ull,ull,ull,ull,int>,bool> mp;

    auto slv = [&](auto slv, ull n0, ull n1, ull n2, ull n3, int i) -> bool {
        char c = str[i];
        bool hisya = (c == 'R' or c == 'Q' or c == 'C' or c == 'M');
        bool kaku = (c == 'B' or c == 'Q' or c == 'A' or c == 'M');
        bool keima = (c == 'A' or c == 'C' or c == 'M');

        if (mp.find({n0,n1,n2,n3,i}) != mp.end()) {
            return mp[{n0,n1,n2,n3,i}];
        }

        ull cp = n0;
        int id = -1;
        while (cp) {
            id += 1;
            if (cp%2 == 0) {
                cp /= 2;
                continue;
            }
            cp /= 2;

            if (hisya) {
                if (n1&bit(id)) continue;
            }
            if (kaku) {
                if (n2&bit(id)) continue;
            }
            if (keima) {
                if (n3&bit(id)) continue;
            }

            ull nn0 = n0;
            ull nn1 = n1;
            ull nn2 = n2;
            ull nn3 = n3;
            nn1 |= ihi[id];
            nn2 |= ika[id];
            nn3 |= ike[id];

            if (hisya) {
                nn0 ^= (nn0&hi[id]);
            }
            if (kaku) {
                nn0 ^= (nn0&ka[id]);
            }
            if (keima) {
                nn0 ^= (nn0&ke[id]);
            }

            auto res = slv(slv, nn0, nn1&nn0, nn2&nn0, nn3&nn0, i+1);
            if (!res) {
                mp[{n0,n1,n2,n3,i}] = true;
                return true;
            }
        }

        mp[{n0,n1,n2,n3,i}] = false;
        return false;
    };

    if (slv(slv, kouho, 0, 0, 0, 0)) {
        cout << "Alice" << endl;
    }
    else {
        cout << "Bob" << endl;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 143ms
memory: 24500kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

score: 0
Accepted
time: 45ms
memory: 12340kb

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

score: 0
Accepted
time: 36ms
memory: 11724kb

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

score: 0
Accepted
time: 52ms
memory: 12640kb

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 88ms
memory: 18736kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

score: 0
Accepted
time: 43ms
memory: 11920kb

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 103ms
memory: 20112kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 623ms
memory: 74068kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

score: 0
Accepted
time: 57ms
memory: 13332kb

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 182ms
memory: 30048kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 130ms
memory: 24488kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 451ms
memory: 59904kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 584ms
memory: 77100kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 1420ms
memory: 163308kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

score: 0
Accepted
time: 78ms
memory: 16720kb

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 243ms
memory: 38460kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed