QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353318#7635. Fairy ChessMisukiAC ✓991ms3964kbC++202.5kb2024-03-14 02:30:122024-03-14 02:30:12

Judging History

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

  • [2024-03-14 02:30:12]
  • 评测
  • 测评结果:AC
  • 用时:991ms
  • 内存:3964kb
  • [2024-03-14 02:30:12]
  • 提交

answer

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

bool OUT(int x, int y) { return !(0 <= x and x < 8 and 0 <= y and y < 8); }

vector<pii> attackSet(int msk, int x, int y) {
    vector<pii> res;
    if (msk & 1) {
        for(int i = 1; i < 8; i++) for(int r1 : {-1, 1}) for(int r2 : {-1, 1})
            if (!OUT(x + r1 * i, y + r2 * i))
                res.emplace_back(x + r1 * i, y + r2 * i);
    }
    if (msk & 2) {
        for(int i = -7; i < 8; i++) {
            if (i != 0 and !OUT(x + i, y))
                res.emplace_back(x + i, y);
            if (i != 0 and !OUT(x, y + i))
                res.emplace_back(x, y + i);
        }
    }
    if (msk & 4) {
        for(int i : {-2, -1, 1, 2})
            for(int j : {-2, -1, 1, 2})
                if (abs(i) != abs(j) and !OUT(x + i, y + j))
                    res.emplace_back(x + i, y + j);
    }
    return res;
}

using board = array<array<bool, 8>, 8>;

vector<pii> pre[8][8][8];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    for(int i = 1; i < 8; i++)
        for(int j = 0; j < 8; j++)
            for(int k = 0; k < 8; k++)
                pre[i][j][k] = attackSet(i, j, k);

    string s; cin >> s;
    array<int, 12> id;
    for(int i = 0; i < 12; i++) {
        char c = s[i];
        if (c == 'B') id[i] = 1;
        if (c == 'R') id[i] = 2;
        if (c == 'Q') id[i] = 3;
        if (c == 'A') id[i] = 5;
        if (c == 'C') id[i] = 6;
        if (c == 'M') id[i] = 7;
    }

    auto dfs = [&](int cnt, board pos, board attacked, auto self) -> bool {
        if (cnt == 12) return false;
        for(int i = 0; i < 8; i++) for(int j = 0; j < 8; j++) if (!attacked[i][j] and !pos[i][j]) {
            bool valid = true;
            for(auto [x, y] : pre[id[cnt]][i][j])
                valid = valid and !pos[x][y];
            if (valid) {
                auto tmp = attacked;
                pos[i][j] = true;
                for(auto [x, y] : pre[id[cnt]][i][j])
                    tmp[x][y] = true;
                if (!self(cnt + 1, pos, tmp, self)) return true;
                pos[i][j] = false;
            }
        }

        return false;
    };

    board init = {};
    cout << (dfs(0, init, init, dfs) ? "Alice\n" : "Bob\n");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 83ms
memory: 3908kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 62ms
memory: 3940kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

score: 0
Accepted
time: 26ms
memory: 3704kb

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 113ms
memory: 3644kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 570ms
memory: 3648kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

score: 0
Accepted
time: 46ms
memory: 3708kb

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 146ms
memory: 3744kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 87ms
memory: 3940kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

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

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 335ms
memory: 3648kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 991ms
memory: 3720kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

score: 0
Accepted
time: 68ms
memory: 3964kb

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

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

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed