QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#230195#7635. Fairy Chessucup-team055#TL 1485ms67448kbC++172.6kb2023-10-28 17:50:482023-10-28 17:50:49

Judging History

This is the latest submission verdict.

  • [2023-10-28 17:50:49]
  • Judged
  • Verdict: TL
  • Time: 1485ms
  • Memory: 67448kb
  • [2023-10-28 17:50:48]
  • Submitted

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(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: 381ms
memory: 21376kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

score: 0
Accepted
time: 181ms
memory: 11356kb

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

score: 0
Accepted
time: 98ms
memory: 8992kb

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

score: 0
Accepted
time: 125ms
memory: 10960kb

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

score: 0
Accepted
time: 211ms
memory: 11524kb

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 206ms
memory: 17252kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

score: 0
Accepted
time: 80ms
memory: 9252kb

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

score: 0
Accepted
time: 102ms
memory: 8348kb

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

score: 0
Accepted
time: 44ms
memory: 6584kb

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

score: 0
Accepted
time: 86ms
memory: 7260kb

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

score: 0
Accepted
time: 101ms
memory: 10820kb

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

score: 0
Accepted
time: 44ms
memory: 6084kb

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

score: 0
Accepted
time: 80ms
memory: 7560kb

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 311ms
memory: 17708kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 1485ms
memory: 63908kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

score: 0
Accepted
time: 167ms
memory: 11968kb

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 543ms
memory: 26072kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 386ms
memory: 21288kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 1138ms
memory: 51540kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 1454ms
memory: 67448kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: -100
Time Limit Exceeded

input:

RAABBRCCQQMM

output:


result: