QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232563#7635. Fairy Chessmendicillin2#WA 1286ms80412kbC++173.4kb2023-10-30 16:31:462023-10-30 16:31:46

Judging History

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

  • [2023-10-30 16:31:46]
  • 评测
  • 测评结果:WA
  • 用时:1286ms
  • 内存:80412kb
  • [2023-10-30 16:31:46]
  • 提交

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

bool can_attack(char type, int x, int y, int ox, int oy) {
	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') {
		for (int ax : {1, 2}) {
			int ay = 3-ax;
			for (int dx : {ax, -ax}) {
				for (int dy : {ay, -ay}) {
					if (x + dx == ox && y + dy == oy) {
						return true;
					}
				}
			}
			return false;
		}
	} 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));
}

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

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

	using C = array<int, 2>;
	using S = array<C, L>;
	using hashing_impl::H;
	const H base = hashing_impl::rand_base();

	using T = pair<int, S>;
	auto encode = [&](int cur, const S& s) -> T {
		/*
		H v = 0;
		for (int i = 0; i < cur; i++) {
			v = v * base + H(9 * (s[i][0]+1) + (s[i][1]+1));
		}
		return ull(v);
		*/
		return T(cur, s);
	};

	using hash_map_impl::hash_map;
	//hash_map<ull, bool> mem;
	map<T, bool> mem;
	auto wins = [&](auto self, int cur, S locs) -> bool {
		if (cur == L) return false;
		T encoded = encode(cur, locs);
		auto it = mem.find(encoded);
		if (it == mem.end()) {
			bool res = [&]() -> bool {
				for (int x = 0; x < 8; x++) {
					for (int y = 0; y < 8; y++) {
						if ([&]() -> bool {
							for (int j = 0; j < cur; j++) {
								if (!works_pair(A[cur], x, y,
											   A[j], locs[j][0], locs[j][1])) {
									return false;
								}
							}
							return true;
						}()) {
							locs[cur] = {x, y};
							if (!self(self, cur+1, locs)) {
								return true;
							}
						} else {
							// do nothing
						}
					}
				}
				return false;
			}();
			it = mem.insert({encoded, res}).first;
		}
		return it->second;
	};
	cout << (wins(wins, 0, S{}) ? "Alice" : "Bob") << '\n';

	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1286ms
memory: 80412kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

score: 0
Accepted
time: 106ms
memory: 9536kb

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

score: -100
Wrong Answer
time: 327ms
memory: 23044kb

input:

QQRAACMRMCBB

output:

Bob

result:

wrong answer 1st lines differ - expected: 'Alice', found: 'Bob'