QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#229286#7635. Fairy Chessucup-team918#AC ✓132ms3740kbC++203.7kb2023-10-28 15:40:222023-10-28 15:40:23

Judging History

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

  • [2023-10-28 15:40:23]
  • 评测
  • 测评结果:AC
  • 用时:132ms
  • 内存:3740kb
  • [2023-10-28 15:40:22]
  • 提交

answer

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
#define mod 998244353
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define ls (rt<<1)
#define rs ((rt<<1)|1)
#define fi first
#define se second
#define INF 1e9
int qpow(int a,int b){
	int res=1;
	for(;b;b>>=1){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
	}
	return res;
}
/*int fac[N],ifac[N];
int C(int n,int m){
	if(m>n||m<0||n<0) return 0;
	return fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}
void init(){
	fac[0]=1;
	for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
	ifac[N-1]=qpow(fac[N-1],mod-2);
	for(int i=N-2;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
}*/
/*struct node{
	int nxt,to;
}e[N<<1];
int cnt=1,head[N];
inline void add(int x,int y){
	e[++cnt].nxt=head[x];
	head[x]=cnt;
	e[cnt].to=y;
}*/
inline int lowbit(int x){return x&(-x);}
inline int read(){
  int x=0,t=1;char ch=getchar();
  while(ch<'0'||ch>'9'){
    if(ch=='-') t=-1;
    ch=getchar();
  }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch-'0');
        ch=getchar();
    }
    return x*t;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
int T,n,c[9][9],d[9][9];
string s;
const int dx[8]={1,1,-1,-1,2,2,-2,-2};
const int dy[8]={2,-2,2,-2,1,-1,1,-1};
const int tx[4]={1,-1,1,-1};
const int tY[4]={-1,1,1,-1};
int deal(char o,int ty,int x,int y){
	int tot=0;
	if(o=='R'||o=='Q'||o=='C'||o=='M'){
		for(int j=1;j<=8;j++){
			if(!c[x][j]) tot++;
			c[x][j]+=ty;
		}	
		for(int j=1;j<=8;j++){
			if(!c[j][y]) tot++;
			c[j][y]+=ty;
		}
	}
	if(o=='Q'||o=='A'||o=='M'||o=='B'){
		for(int k=0;k<4;k++){
			int nowx=x,nowy=y;
			while(nowx>=1&&nowx<=8&&nowy>=1&&nowy<=8){
				if(!c[nowx][nowy]) tot++;
				c[nowx][nowy]+=ty;
				nowx+=tx[k];nowy+=tY[k];
			}
		}
	}
	if(o=='A'||o=='C'||o=='M'){
		for(int k=0;k<8;k++){
			int nx=x+dx[k],ny=y+dy[k];
			if(nx>=1&&nx<=8&&ny>=1&&ny<=8){
				if(!c[nx][ny]) tot++;
				c[nx][ny]+=ty;
			}
		}
		if(!c[x][y]) tot++;
		c[x][y]+=ty;
	}
	return tot;
}
int check(int x,int y,char o){
	if(o=='R'||o=='Q'||o=='C'||o=='M'){
		for(int j=1;j<=8;j++)
			if(d[x][j]) return 1;
		for(int j=1;j<=8;j++)
			if(d[j][y]) return 1;
	}
	if(o=='Q'||o=='A'||o=='M'||o=='B'){
		for(int k=0;k<4;k++){
			int nowx=x,nowy=y;
			while(nowx>=1&&nowx<=8&&nowy>=1&&nowy<=8){
				if(d[nowx][nowy]) return 1;
				nowx+=tx[k];nowy+=tY[k];
			}
		}
	}
	if(o=='A'||o=='C'||o=='M'){
		for(int k=0;k<8;k++){
			int nx=x+dx[k],ny=y+dy[k];
			if(nx>=1&&nx<=8&&ny>=1&&ny<=8){
				if(d[nx][ny]) return 1;
			}
		}
	}
	return 0;
}
int solve(int now,int tot){
	if(now==12) return 1;
	int turn=now%2;
	int t=8;if(now==0) t=4;
	for(int i=1;i<=t;i++)
		for(int j=1;j<=t;j++){
			if(c[i][j]) continue;
			if(check(i,j,s[now])) continue;
			int rr=deal(s[now],1,i,j);
			d[i][j]=1;
			if(rr+tot==64){
				deal(s[now],-1,i,j);
				d[i][j]=0;
				return turn;
			}
			if(rr>=10){
				int w=solve(now+1,tot+rr);
				if(w==turn){
					deal(s[now],-1,i,j);
					d[i][j]=0;
					return w;
				}
			}
			deal(s[now],-1,i,j);
			d[i][j]=0;
		}
	for(int i=1;i<=t;i++)
		for(int j=1;j<=t;j++){
			if(c[i][j]) continue;
			if(check(i,j,s[now])) continue;
			int rr=deal(s[now],1,i,j);
			d[i][j]=1;
			if(rr<10){
				int w=solve(now+1,tot+rr);
				if(w==turn){
					deal(s[now],-1,i,j);
					d[i][j]=0;
					return w;
				}
			}
			deal(s[now],-1,i,j);
			d[i][j]=0;
		}
	//	cout<<now<<" "<<turn<<endl;
	return (turn^1);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>s;
	int res=solve(0,0);
	if(res==0) cout<<"Alice"<<endl;
	else cout<<"Bob"<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 19ms
memory: 3736kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

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

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

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: 7ms
memory: 3608kb

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

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

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

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

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

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

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

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

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

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

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

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

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed