QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235094#7635. Fairy Chessucup-team870#AC ✓205ms3852kbC++142.7kb2023-11-02 13:47:222023-11-02 13:47:22

Judging History

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

  • [2023-11-02 13:47:22]
  • 评测
  • 测评结果:AC
  • 用时:205ms
  • 内存:3852kb
  • [2023-11-02 13:47:22]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
const int N = 10;

char s[100];
int vis[N][N];
int cnt[4][N*2], stone[N][N];

int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

bool check(int x, int y, char c) {
    if (c == 'B' || c == 'A') {
        if (cnt[2][x-y+8] || cnt[3][x+y]) return true;
    }
    if (c == 'R' || c == 'C') {
        if (cnt[0][x] || cnt[1][y]) return  true;
    }
    if (c == 'Q' || c == 'M') {
        if (cnt[2][x-y+8] || cnt[3][x+y] || cnt[0][x] || cnt[1][y]) return true;
    }
    if (c == 'A' || c == 'C' || c == 'M') {
        rep (k, 0, 7) {
            int tx = x + dx[k], ty = y + dy[k];
            if (tx >= 1 && tx <= 8 && ty >= 1 && ty <= 8) {
                if (stone[tx][ty]) return true;
            }
        }
    }
    return false;
}

void place(int x, int y, const int K, char c) {
    // vis[x][y] += K;
    cnt[0][x] += K;
    cnt[1][y] += K;
    cnt[2][x-y+8] += K;
    cnt[3][x+y] += K;
    stone[x][y]+=K;
    if (c == 'B' || c == 'A') {
        rep (i, -8, 8) {
            int tx = x+i, ty = y+i;
            if (tx>=1&&tx<=8&&ty>=1&&ty<=8) vis[tx][ty]+=K;
            tx = x+i, ty = y-i;
            if (tx>=1&&tx<=8&&ty>=1&&ty<=8) vis[tx][ty]+=K;
        }
    }
    if (c == 'R' || c == 'C') {
        rep (i, 1, 8) vis[x][i] += K, vis[i][y] += K;
    }
    if (c == 'Q' || c == 'M') {
        rep (i, 1, 8) {
            vis[x][i] += K, vis[i][y] += K;
        }
        rep (i, -8, 8) {
            int tx = x+i, ty = y+i;
            if (tx>=1&&tx<=8&&ty>=1&&ty<=8) vis[tx][ty]+=K;
            tx = x+i, ty = y-i;
            if (tx>=1&&tx<=8&&ty>=1&&ty<=8) vis[tx][ty]+=K;
        }
    }
    if (c == 'A' || c == 'C' || c == 'M') {
        rep (k, 0, 7) {
            int tx = x + dx[k], ty = y + dy[k];
            if (tx >= 1 && tx <= 8 && ty >= 1 && ty <= 8) {
                vis[tx][ty] += K;
            }
        }
    }
}

bool dfs(int c) {
    // cout <<c;
    if (c == 13) return false;
    int xx = 8;
    if (c == 1) xx = 4;
    rep (i, 1, xx) {
        rep (j, 1, xx) {
            if (!vis[i][j]) {
                if (!check(i, j, s[c])) {
                    place(i, j, 1, s[c]);
                    int flag = dfs(c+1);
                    place(i, j, -1, s[c]);
                    if (flag == 0) return true;
                }
            }
        }
    }
    return false;
}

int main() {
    scanf("%s", s+1);
    if (dfs(1)) puts("Alice");
    else puts("Bob");
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 17ms
memory: 3848kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

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

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 205ms
memory: 3724kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

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

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 61ms
memory: 3784kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

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

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

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

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 83ms
memory: 3724kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed