QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#230234#7635. Fairy Chessucup-team055#AC ✓1052ms49776kbC++172.6kb2023-10-28 17:55:582023-10-28 17:55:58

Judging History

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

  • [2023-10-28 17:55:58]
  • 评测
  • 测评结果:AC
  • 用时:1052ms
  • 内存:49776kb
  • [2023-10-28 17:55:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)


void solve(){
    string S;
    cin>>S;
    int N=S.size();
    vector<vector<int>> p(N,vector<int>(3));//(kaku,hisya,keima)
    rep(i,0,N) {
        if (S[i] == 'B') p[i][0] = 1;
        if (S[i] == 'R') p[i][1] = 1;
        if (S[i] == 'Q') p[i][0] = 1, p[i][1] = 1;
        if (S[i] == 'A') p[i][0] = 1, p[i][2] = 1;
        if (S[i] == 'C') p[i][1] = 1, p[i][2] = 1;
        if (S[i] == 'M') p[i][0] = 1, p[i][1] = 1, p[i][2] = 1;
    }
    const int M=8;
    vector<vector<int>> ban(M,vector<int>(M));
    vector<vector<int>> table(M,vector<int>(M));
    vector<int> dx={2,2,1,1,-1,-1,-2,-2};
    vector<int> dy={1,-1,2,-2,2,-2,1,-1};
    auto ins=[&](int a,int b) -> bool {
        return 0<=min(a,b)&&max(a,b)<M;
    };
    ll B=0,T=0;
    auto g=[&](int x,int y,int val) -> bool {
        if(!ins(x,y)) return true;
        ban[x][y]+=val;
        int z=x*M+y;
        B=(B|(1ll<<z));
        if(ban[x][y]==0) B-=(1ll<<z);
        return (0==table[x][y]);
    };
    auto pu=[&](int x,int y,int ind,int val) -> bool {
        bool res=1;
        if(table[x][y]) res=0;
        if(p[ind][0]){
            rep(i,-M,M){
                int s,t;
                s=x+i,t=y+i;
                res&=g(s,t,val);
                s=x+i,t=y-i;
                res&=g(s,t,val);
            }
        }
        if(p[ind][1]){
            rep(i,0,M){
                res&=g(i,y,val);
                res&=g(x,i,val);
            }
        }
        if(p[ind][2]){
            rep(i,0,M){
                int s=x+dx[i];
                int t=y+dy[i];
                res&=g(s,t,val);
            }
        }
        table[x][y]+=val;
        T=(T|(1ll<<(x*M+y)));
        if(table[x][y]==0) T-=(1ll<<(x*M+y));
        return res;
    };
    map<tuple<int,ll,ll>,bool> m;
    auto f=[&](auto self,int ind) -> bool {
        if(ind==N) return false;
        if(m.count({ind,B,T})) return m[{ind,B,T}];
        rep(i,0,8) rep(j,0,8){
            if(ind==0&&max(i,j)>=4) break;
            if(ban[i][j]) continue;
            auto tmp=pu(i,j,ind,1);bool res=1;
            if(tmp){
                res=self(self,ind+1);
            }
            pu(i,j,ind,-1);
            if(!res){
                m[{ind,B,T}]=1;
                return true;
            }
        }
        m[{ind,B,T}]=0;
        return false;
    };
    auto ans=f(f,0);
    cout<<(ans?"Alice\n":"Bob\n");
}

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

// BBAARRCCQQMM

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 104ms
memory: 9164kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

score: 0
Accepted
time: 24ms
memory: 4980kb

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

score: 0
Accepted
time: 47ms
memory: 5800kb

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

score: 0
Accepted
time: 123ms
memory: 9176kb

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 67ms
memory: 8324kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

score: 0
Accepted
time: 33ms
memory: 5748kb

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

score: 0
Accepted
time: 96ms
memory: 8332kb

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

score: 0
Accepted
time: 33ms
memory: 5928kb

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

score: 0
Accepted
time: 24ms
memory: 4824kb

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 141ms
memory: 10676kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 1052ms
memory: 49776kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

score: 0
Accepted
time: 161ms
memory: 12252kb

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 161ms
memory: 11008kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 108ms
memory: 9100kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 292ms
memory: 17820kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 137ms
memory: 10712kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 778ms
memory: 39848kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

score: 0
Accepted
time: 91ms
memory: 7444kb

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 460ms
memory: 25368kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed