QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#228025#7635. Fairy Chessucup-team1209#AC ✓931ms139792kbC++201.8kb2023-10-28 10:46:132023-10-28 10:46:14

Judging History

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

  • [2023-10-28 10:46:14]
  • 评测
  • 测评结果:AC
  • 用时:931ms
  • 内存:139792kb
  • [2023-10-28 10:46:13]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin, std::cout;
int n, m;
using u64 = unsigned long long;
using u128 = __int128_t;
std::map<u128, int> map[15];
u64 atk[256][64];
int id(int x, int y) { return x * 8 + y; }
char c[100];
u128 mp(u64 x, u64 y) {
	return (u128) x << 64 | y;
}
u64 sid(int x, int y) {
	if(x < 0 || x >= 8) return 0;
	if(y < 0 || y >= 8) return 0;
	return 1ull << id(x, y);
}
bool dfs(u64 s, u64 place, int id) {
	if(s == 0 || id == 12) {
		return 0;
	}
	u128 state = mp(place, s);
	auto iter = map[id].find(state);
	if(iter != map[id].end()) return iter -> second;
	int & ans = map[id][state];
	for(u64 x = s;x;x &= x - 1) {
		int p = __builtin_ctzll(x);
		if(place & atk[c[id]][p]) {
			continue;
		}
		ans = ans || !dfs(s & ~atk[c[id]][p], place | 1ull << p, id + 1);
	}
	return ans;
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	for(int i = 0;i < 8;++i) {
		for(int j = 0;j < 8;++j) {
			for(int k = 0;k < 8;++k) {
				atk['R'][id(i, j)] |= 1ull << id(i, k);
				atk['R'][id(i, j)] |= 1ull << id(k, j);
				atk['B'][id(i, j)] |= sid(i + k, j + k);
				atk['B'][id(i, j)] |= sid(i + k, j - k);
				atk['B'][id(i, j)] |= sid(i - k, j + k);
				atk['B'][id(i, j)] |= sid(i - k, j - k);
			}
			atk['K'][id(i, j)] |= sid(i, j);
			for(int u : {2, -2})
				for(int v : {1, -1}) {
					atk['K'][id(i, j)] |= sid(i + u, j + v);
					atk['K'][id(i, j)] |= sid(i + v, j + u);
				}
			atk['Q'][id(i, j)] = atk['R'][id(i, j)] | atk['B'][id(i, j)];
			atk['A'][id(i, j)] = atk['B'][id(i, j)] | atk['K'][id(i, j)];
			atk['C'][id(i, j)] = atk['R'][id(i, j)] | atk['K'][id(i, j)];
			atk['M'][id(i, j)] = atk['Q'][id(i, j)] | atk['K'][id(i, j)];
		}
	}
	cin >> c;
	cout << (dfs(-1ull, 0, 0) ? "Alice" : "Bob") << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 77ms
memory: 21344kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 58ms
memory: 17192kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 384ms
memory: 63640kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

score: 0
Accepted
time: 32ms
memory: 12056kb

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 99ms
memory: 26144kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 81ms
memory: 21404kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 257ms
memory: 51588kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 340ms
memory: 67412kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 931ms
memory: 139792kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

score: 0
Accepted
time: 48ms
memory: 15084kb

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 137ms
memory: 33284kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed