QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#232558 | #7635. Fairy Chess | mendicillin2# | WA | 976ms | 38012kb | C++17 | 3.4kb | 2023-10-30 16:29:32 | 2023-10-30 16:29:32 |
Judging History
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();
auto encode = [&](int cur, const S& s) -> ull {
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);
};
using hash_map_impl::hash_map;
//hash_map<ull, bool> mem;
map<ull, bool> mem;
auto wins = [&](auto self, int cur, S locs) -> bool {
if (cur == L) return false;
ull 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 976ms
memory: 38012kb
input:
BBAARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 78ms
memory: 6268kb
input:
BAMBAMQQRCCR
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: -100
Wrong Answer
time: 268ms
memory: 12372kb
input:
QQRAACMRMCBB
output:
Bob
result:
wrong answer 1st lines differ - expected: 'Alice', found: 'Bob'