QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227617#7635. Fairy Chessucup-team1447#AC ✓770ms107812kbC++142.5kb2023-10-27 19:49:332023-10-27 19:49:33

Judging History

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

  • [2023-10-27 19:49:33]
  • 评测
  • 测评结果:AC
  • 用时:770ms
  • 内存:107812kb
  • [2023-10-27 19:49:33]
  • 提交

answer

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
using ull = unsigned long long;
std::string s;
struct hsh
{
    std::size_t operator()(const std::pair<ull, ull> &x) const { return x.second; }
};
std::unordered_map<std::pair<ull, ull>, bool, hsh> map;
ull B[64], R[64], K[64], Q[64], A[64], C[64], M[64];
int id(int x, int y) { return x << 3 | y; }
ull g(int pos, char type)
{
    switch (type)
    {
    case 'B':
        return B[pos];
    case 'R':
        return R[pos];
    case 'Q':
        return Q[pos];
    case 'A':
        return A[pos];
    case 'C':
        return C[pos];
    case 'M':
        return M[pos];
    default:
        return K[pos];
    }
}
bool dfs(ull x, ull y, int z)
{
    static int cnt;
    ++cnt;
    if (map.count({x, y}))
        return map[{x, y}];
    bool &res = map[{x, y}];
    for (int i = 0; i != 64; ++i)
        if (~x >> i & 1 && !(y & g(i, s[z]))){
        	res |= !dfs(x | g(i, s[z]), y | 1llu << i, z + 1);
        	if(res==1) return res;
		}
            
    return res;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    for (int i = 0; i != 8; ++i)
        for (int j = 0; j != 8; ++j)
        {
            for (int k = -8; k != 8; ++k)
            {
                if (i + k >= 0 && j + k >= 0 && i + k < 8 && j + k < 8)
                    B[id(i, j)] |= 1llu << id(i + k, j + k);
                if (i + k >= 0 && j - k >= 0 && i + k < 8 && j - k < 8)
                    B[id(i, j)] |= 1llu << id(i + k, j - k);
            }
            for (int k = -8; k != 8; ++k)
            {
                if (i + k >= 0 && j >= 0 && i + k < 8 && j < 8)
                    R[id(i, j)] |= 1llu << id(i + k, j);
                if (i >= 0 && j + k >= 0 && i < 8 && j + k < 8)
                    R[id(i, j)] |= 1llu << id(i, j + k);
            }
            for (int iv = -2; iv <= 2; ++iv)
                for (int jv = -2; jv <= 2; ++jv)
                    if (std::abs(iv) + std::abs(jv) == 3 && i + iv >= 0 && j + jv >= 0 && i + iv < 8 && j + jv < 8)
                        K[id(i, j)] |= 1llu << id(i + iv, j + jv);
            K[id(i, j)] |= 1llu << id(i, j);
            Q[id(i, j)] = B[id(i, j)] | R[id(i, j)];
            A[id(i, j)] = B[id(i, j)] | K[id(i, j)];
            C[id(i, j)] = R[id(i, j)] | K[id(i, j)];
            M[id(i, j)] = Q[id(i, j)] | K[id(i, j)];
        }
    std::cin >> s;
    std::cout << (dfs(0, 0, 0) ? "Alice" : "Bob") << std::endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 60ms
memory: 16580kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

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

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 258ms
memory: 53616kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 76ms
memory: 19324kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 60ms
memory: 16576kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 191ms
memory: 37608kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 271ms
memory: 53540kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 770ms
memory: 107812kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

score: 0
Accepted
time: 40ms
memory: 11584kb

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 97ms
memory: 28068kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed