QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#231236#7635. Fairy Chessucup-team1134#AC ✓1749ms112376kbC++173.0kb2023-10-29 04:17:072023-10-29 04:17:07

Judging History

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

  • [2023-10-29 04:17:07]
  • 评测
  • 测评结果:AC
  • 用时:1749ms
  • 内存:112376kb
  • [2023-10-29 04:17:07]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;

map<pair<ull,ull>,bool> MA[15];

string S;

vector<int> dh={1,2,2,1,-1,-2,-2,-1},dw={2,1,-1,-2,-2,-1,1,2};

bool solve(int u,ull ng,ull put){
    if(u==12) return false;
    if(MA[u].count(mp(ng,put))) return MA[u][mp(ng,put)];
    
    vector<int> type(3);
    if(S[u]!='R'&&S[u]!='C') type[0]=1;
    if(S[u]!='B'&&S[u]!='A') type[1]=1;
    if(S[u]=='A'||S[u]=='C'||S[u]=='M') type[2]=1;
    
    for(int a=0;a<8;a++){
        for(int b=0;b<8;b++){
            if((ng&(1uLL<<(a*8+b)))>0) continue;
            
            bool ok=true;
            
            ull nng=ng,nput=put;
            
            if(type[0]){
                for(int i=0;i<8;i++){
                    int j=a+b-i;
                    if(0<=j&&j<8){
                        if((put&(1uLL<<(i*8+j)))>0) ok=false;
                        nng|=(1uLL<<(i*8+j));
                    }
                }
                if(!ok) continue;
                
                for(int i=0;i<8;i++){
                    int j=i-(a-b);
                    if(0<=j&&j<8){
                        if((put&(1uLL<<(i*8+j)))>0) ok=false;
                        nng|=(1uLL<<(i*8+j));
                    }
                }
                if(!ok) continue;
            }
            
            if(type[1]){
                for(int i=0;i<8;i++){
                    int j=b;
                    if((put&(1uLL<<(i*8+j)))>0) ok=false;
                    nng|=(1uLL<<(i*8+j));
                }
                if(!ok) continue;
                
                for(int j=0;j<8;j++){
                    int i=a;
                    if((put&(1uLL<<(i*8+j)))>0) ok=false;
                    nng|=(1uLL<<(i*8+j));
                }
                if(!ok) continue;
            }
            
            if(type[2]){
                for(int k=0;k<8;k++){
                    int i=a+dh[k],j=b+dw[k];
                    if(0<=i&&i<8&&0<=j&&j<8){
                        if((put&(1uLL<<(i*8+j)))>0) ok=false;
                        nng|=(1uLL<<(i*8+j));
                    }
                }
                if(!ok) continue;
            }
            
            nput|=(1uLL<<(a*8+b));
            
            if(!solve(u+1,nng,nput)) return MA[u][mp(ng,put)]=true;
        }
    }
    
    return MA[u][mp(ng,put)]=false;
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>S;
    if(solve(0,0,0)) cout<<"Alice\n";
    else cout<<"Bob\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 151ms
memory: 17664kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

score: 0
Accepted
time: 43ms
memory: 7812kb

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

score: 0
Accepted
time: 52ms
memory: 9188kb

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

score: 0
Accepted
time: 73ms
memory: 9852kb

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

score: 0
Accepted
time: 30ms
memory: 7172kb

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 106ms
memory: 14288kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

score: 0
Accepted
time: 35ms
memory: 7212kb

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

score: 0
Accepted
time: 30ms
memory: 6332kb

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

score: 0
Accepted
time: 50ms
memory: 9244kb

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 797ms
memory: 51512kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

score: 0
Accepted
time: 79ms
memory: 10140kb

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 240ms
memory: 21400kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 151ms
memory: 17688kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 565ms
memory: 41828kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 752ms
memory: 54572kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 1749ms
memory: 112376kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

score: 0
Accepted
time: 106ms
memory: 12652kb

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 290ms
memory: 27212kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed