QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232591#7635. Fairy Chessmendicillin2#AC ✓156ms3560kbC++173.2kb2023-10-30 17:08:052023-10-30 17:08:05

Judging History

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

  • [2023-10-30 17:08:05]
  • 评测
  • 测评结果:AC
  • 用时:156ms
  • 内存:3560kb
  • [2023-10-30 17:08:05]
  • 提交

answer

#pragma GCC optimize ("Ofast")
#include <bits/extc++.h>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

namespace hash_map_impl {

struct custom_hash {
	static const uint64_t c = ll(4e18 * acos(0)) + 71;
	const ll z = mt();
	ll operator ()(ll x) const { return __builtin_bswap64((x ^ z) * c); }
};

template <class K, class V>
using hash_map = __gnu_pbds::gp_hash_table<K, V, custom_hash>;

} // namespace hash_map_impl

namespace hashing_impl {

struct H {
	ull x;
	H(ull x_ = 0) : x(x_) {}
#define OP(O,A,B) H operator O(H o) { ull r = x; asm \
	(A "addq %%rdx, %0\n adcq $0,%0" : "+a"(r) : B); return r; }
	OP(+,,"d"(o.x)) OP(*,"mul %1\n", "r"(o.x) : "rdx")
	H operator - (H o) { return *this + H(~o.x); }
	explicit operator ull() const { return x + !~x; }
	bool operator == (H o) const { return ull(*this) == ull(o); }
	bool operator < (H o) const { return ull(*this) < ull(o); }
};

H rand_base() {
	return H(2 * uniform_int_distribution<ll>(4e10, 5e10)(mt) + 1);
}

} // namespace hashing_impl

int get_idx(int x, int y) {
	return 8 * x + y;
}

bool can_attack(char type, int x, int y, int ox, int oy) {
	if (x == ox && y == oy) return true;
	if (type == 'B') {
		return x+y == ox+oy || x-y == ox-oy;
	} else if (type == 'R') {
		return x == ox || y == oy;
	} else if (type == 'Q') {
		return can_attack('B', x, y, ox, oy)
			|| can_attack('R', x, y, ox, oy);
	} else if (type == 'K') {
		return (x - ox) * (x - ox) + (y - oy) * (y - oy) == 5;
	} else if (type == 'C') {
		return can_attack('R', x, y, ox, oy)
			|| can_attack('K', x, y, ox, oy);
	} else if (type == 'M') {
		return can_attack('Q', x, y, ox, oy)
			|| can_attack('K', x, y, ox, oy);
	} else if (type == 'A') {
		return can_attack('B', x, y, ox, oy)
			|| can_attack('K', x, y, ox, oy);
	} assert(false);
}

bool works_pair(char t, int x, int y, char ot, int ox, int oy) {
	if (x == ox && y == oy) return false;
	return !(can_attack(t, x, y, ox, oy)
			 || can_attack(ot, ox, oy, x, y));
}

constexpr int K = 6;
const string types = "BRQACM";
ull occ[K][64];

void precomp() {
	assert(int(types.size()) == K);
	for (int k = 0; k < K; k++) {
		char t = types[k];
		for (int x = 0; x < 8; x++) {
			for (int y = 0; y < 8; y++) {
				for (int ox = 0; ox < 8; ox++) {
					for (int oy = 0; oy < 8; oy++) {
						if (can_attack(t, x, y, ox, oy)) {
							occ[k][get_idx(x, y)] |= ull(1) << get_idx(ox, oy);
						}
					}
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	precomp();

	string A_; cin >> A_;
	constexpr int L = 12;
	assert(int(A_.size()) == L);

	array<int, L> A;
	for (int i = 0; i < L; i++) {
		int k = types.find(A_[i]);
		assert(0 <= k && k < 6);
		A[i] = k;
	}

	auto wins = [&](auto self, int cur, ull used, ull banned) -> bool {
		if (cur == L) return false;
		bool res = [&]() -> bool {
			int k = A[cur];
			ull free = ~banned;
			while (free > 0) {
				int g = __builtin_ctzll(free);
				if (!(occ[k][g] & used) && !self(self, cur+1, used | (ull(1) << g), banned | occ[k][g])) {
					return true;
				}
				free -= ull(1) << g;
			}
			return false;
		}();
		return res;
	};
	cout << (wins(wins, 0, 0, 0) ? "Alice" : "Bob") << '\n';

	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 17ms
memory: 3436kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

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

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 89ms
memory: 3376kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

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

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

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

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

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

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 156ms
memory: 3420kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 29ms
memory: 3484kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed