QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#229024#7635. Fairy Chessucup-team022#AC ✓1706ms3808kbC++171.7kb2023-10-28 14:50:462023-10-28 14:50:47

Judging History

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

  • [2023-10-28 14:50:47]
  • 评测
  • 测评结果:AC
  • 用时:1706ms
  • 内存:3808kb
  • [2023-10-28 14:50:46]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1e9, n = 8;
typedef pair<int, int> pr;
string str;
int t[10][10], has[10][10];
// t: 之前能攻击到的
// has: 之前有的
vector<pr> V = {pr(-1, -2), pr(-1, 2), pr(1, 2),  pr(1, -2),
                pr(2, 1),   pr(2, -1), pr(-2, 1), pr(-2, -1)};
bool Put(char ch, int x, int y) {
	int at[10][10];
	memcpy(at, t, sizeof(t));
	if (ch == 'B' || ch == 'A' || ch == 'Q' || ch == 'M') {
		for (int i = -1; i <= 1; i += 2) {
			for (int j = -1; j <= 1; j += 2) {
				int tx = x, ty = y;
				while (tx >= 1 && tx <= n && ty >= 1 && ty <= n) {
					if (has[tx][ty]) return 0;
					at[tx][ty]++;
					tx += i, ty += j;
				}
			}
		}
	}
	if (ch == 'R' || ch == 'C' || ch == 'Q' || ch == 'M') {
		for (int i = -1; i <= 1; i += 2) {
			for (int j = -1; j <= 1; j += 2) {
				int tx = x, ty = y;
				while (tx >= 1 && tx <= n && ty >= 1 && ty <= n) {
					if (has[tx][ty]) return 0;
					at[tx][ty]++;
					tx += (i + j) / 2, ty += (i - j) / 2;
				}
			}
		}
	}
	if (ch == 'A' || ch == 'C' || ch == 'M') {
		for (auto [i, j] : V) {
			int tx = x + i, ty = y + j;
			if (tx >= 1 && tx <= n && ty >= 1 && ty <= n) {
				if (has[tx][ty]) return 0;
				at[tx][ty]++;
			}
		}
	}
	memcpy(t, at, sizeof(t));
	return 1;
}
bool dfs(int x) {
	for (int i = 1; i <= 8; i++) {
		for (int j = 1; j <= 8; j++) {
			if (t[i][j]) continue;
			int tt[10][10];
			memcpy(tt, t, sizeof(t));
			if (Put(str[x], i, j)) {
				has[i][j] = 1;
				if (!dfs(x + 1)) {
					memcpy(t, tt, sizeof(t));
					has[i][j] = 0;
					return 1;
				}
				has[i][j] = 0;
				memcpy(t, tt, sizeof(t));
			}
		}
	}
	return 0;
}
int main() {
	cin >> str;
	cout << (dfs(0) ? "Alice" : "Bob");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 167ms
memory: 3540kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

score: 0
Accepted
time: 42ms
memory: 3600kb

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

score: 0
Accepted
time: 42ms
memory: 3804kb

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

score: 0
Accepted
time: 71ms
memory: 3600kb

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 94ms
memory: 3808kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

score: 0
Accepted
time: 41ms
memory: 3536kb

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

score: 0
Accepted
time: 16ms
memory: 3516kb

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

score: 0
Accepted
time: 27ms
memory: 3508kb

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 216ms
memory: 3804kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 968ms
memory: 3512kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

score: 0
Accepted
time: 84ms
memory: 3592kb

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

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

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 577ms
memory: 3544kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 558ms
memory: 3544kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 1706ms
memory: 3564kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

score: 0
Accepted
time: 117ms
memory: 3796kb

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 315ms
memory: 3768kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed