QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#232591 | #7635. Fairy Chess | mendicillin2# | AC ✓ | 156ms | 3560kb | C++17 | 3.2kb | 2023-10-30 17:08:05 | 2023-10-30 17:08:05 |
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
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;
}
Details
Tip: Click on the bar to expand more detailed information
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