QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#610567#7635. Fairy ChessericmegalovaniaAC ✓348ms3752kbC++202.7kb2024-10-04 16:29:062024-10-04 16:29:07

Judging History

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

  • [2024-10-04 16:29:07]
  • 评测
  • 测评结果:AC
  • 用时:348ms
  • 内存:3752kb
  • [2024-10-04 16:29:06]
  • 提交

answer

#include<bits/stdc++.h> //bf + bit mask + sg
using namespace std;

#define ONLINE
#ifndef ONLINE
char DEBUG_BUFFER[1000];
#define debug(...) {sprintf(DEBUG_BUFFER,##__VA_ARGS__);\
cerr<<"\033[1;36m"<<DEBUG_BUFFER<<"\033[0;2m"<<"\033[0m";}
#else
#define debug(...) ;
#endif

using LL=long long;
using PII=pair<int,int>;

#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()

#define FAST_IO {ios::sync_with_stdio(false);cin.tie(nullptr);}
inline int read(){static int x; cin>>x; return x;}
inline LL readLL(){static LL x; cin>>x; return x;}
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

using u64=unsigned long long;

u64 cover[6][64];
inline int pos(const int& x,const int& y){
	return x*8+y;
}
inline void upd(u64& res,const int& x,const int& y){
	if(x>=0 && x<8 && y>=0 && y<8){
		res|=1ull<<pos(x,y);
	}
}
void init(){
	int dir[8][2]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
	for(int x=0;x<8;x++) for(int y=0;y<8;y++){
		int id=pos(x,y);
		u64 knight=0;
		for(int i=0;i<8;i++){
			int dx=dir[i][0],dy=dir[i][1];
			upd(knight,x+dx,y+dy);
		}
		for(int i=-8;i<8;i++){
			//bishop
			upd(cover[0][id],x+i,y+i);
			upd(cover[0][id],x+i,y-i);
			//rook
			upd(cover[1][id],x+i,y);
			upd(cover[1][id],x,y+i);
		}
		//queen
		cover[2][id]=cover[0][id]|cover[1][id];
		//archbishop
		cover[3][id]=knight|cover[0][id];
		//chancellor
		cover[4][id]=knight|cover[1][id];
		//maharaja
		cover[5][id]=knight|cover[2][id];
//		for(int j=0;j<6;j++){
//			assert(cover[j][id]>>id&1);
//		}
	}
}

string s;
int a[12];
inline int c2i(const char& c){
	if(c=='B') return 0;
	else if(c=='R') return 1;
	else if(c=='Q') return 2;
	else if(c=='A') return 3;
	else if(c=='C') return 4;
	else return 5; //'M'
}

bool dfs(const u64& cov,const u64& put,const int& u){
	debug("%llu %llu %d|%d\n",cov,put,u,a[u]);
	if(u==12) return 0;
	for(int i=0;i<64;i++){
		if(cov>>i&1){
			debug("\tfuck %llu %d\n",cov,i);
		}
		else{
			if(cover[a[u]][i]&put) debug("\t%d %d fail\n",u,i);
			if(cover[a[u]][i]&put) continue;
			debug("\t%d %d\n",u,i);
			if(!dfs(cov|cover[a[u]][i],put|1ull<<i,u+1)){
				return 1;
			}
		}
	}
	return 0;
}

int main(){
	FAST_IO;
	init();
	assert(!(cover[0][0]>>2&1));
	assert(!(cover[0][1]>>2&1));
	assert(!((cover[0][0]|cover[0][1])>>2&1));
	debug("%llu\n",cover[0][0]|cover[0][1]);
	cin>>s;
	for(int i=0;i<12;i++) a[i]=c2i(s[i]);
	cout<<(dfs(0,0,0)?"Alice":"Bob");
	return 0;
}

/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 33ms
memory: 3712kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

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

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 202ms
memory: 3552kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

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

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

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

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

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

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

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

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 66ms
memory: 3560kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed