QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227617 | #7635. Fairy Chess | ucup-team1447# | AC ✓ | 770ms | 107812kb | C++14 | 2.5kb | 2023-10-27 19:49:33 | 2023-10-27 19:49:33 |
Judging History
answer
// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
using ull = unsigned long long;
std::string s;
struct hsh
{
std::size_t operator()(const std::pair<ull, ull> &x) const { return x.second; }
};
std::unordered_map<std::pair<ull, ull>, bool, hsh> map;
ull B[64], R[64], K[64], Q[64], A[64], C[64], M[64];
int id(int x, int y) { return x << 3 | y; }
ull g(int pos, char type)
{
switch (type)
{
case 'B':
return B[pos];
case 'R':
return R[pos];
case 'Q':
return Q[pos];
case 'A':
return A[pos];
case 'C':
return C[pos];
case 'M':
return M[pos];
default:
return K[pos];
}
}
bool dfs(ull x, ull y, int z)
{
static int cnt;
++cnt;
if (map.count({x, y}))
return map[{x, y}];
bool &res = map[{x, y}];
for (int i = 0; i != 64; ++i)
if (~x >> i & 1 && !(y & g(i, s[z]))){
res |= !dfs(x | g(i, s[z]), y | 1llu << i, z + 1);
if(res==1) return res;
}
return res;
}
signed main()
{
std::ios::sync_with_stdio(false);
for (int i = 0; i != 8; ++i)
for (int j = 0; j != 8; ++j)
{
for (int k = -8; k != 8; ++k)
{
if (i + k >= 0 && j + k >= 0 && i + k < 8 && j + k < 8)
B[id(i, j)] |= 1llu << id(i + k, j + k);
if (i + k >= 0 && j - k >= 0 && i + k < 8 && j - k < 8)
B[id(i, j)] |= 1llu << id(i + k, j - k);
}
for (int k = -8; k != 8; ++k)
{
if (i + k >= 0 && j >= 0 && i + k < 8 && j < 8)
R[id(i, j)] |= 1llu << id(i + k, j);
if (i >= 0 && j + k >= 0 && i < 8 && j + k < 8)
R[id(i, j)] |= 1llu << id(i, j + k);
}
for (int iv = -2; iv <= 2; ++iv)
for (int jv = -2; jv <= 2; ++jv)
if (std::abs(iv) + std::abs(jv) == 3 && i + iv >= 0 && j + jv >= 0 && i + iv < 8 && j + jv < 8)
K[id(i, j)] |= 1llu << id(i + iv, j + jv);
K[id(i, j)] |= 1llu << id(i, j);
Q[id(i, j)] = B[id(i, j)] | R[id(i, j)];
A[id(i, j)] = B[id(i, j)] | K[id(i, j)];
C[id(i, j)] = R[id(i, j)] | K[id(i, j)];
M[id(i, j)] = Q[id(i, j)] | K[id(i, j)];
}
std::cin >> s;
std::cout << (dfs(0, 0, 0) ? "Alice" : "Bob") << std::endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 60ms
memory: 16580kb
input:
BBAARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 4ms
memory: 4448kb
input:
BAMBAMQQRCCR
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: 0
Accepted
time: 2ms
memory: 4112kb
input:
QQRAACMRMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #4:
score: 0
Accepted
time: 3ms
memory: 5104kb
input:
MBBARQRMACQC
output:
Alice
result:
ok single line: 'Alice'
Test #5:
score: 0
Accepted
time: 2ms
memory: 4012kb
input:
ACQCMQRBBRMA
output:
Alice
result:
ok single line: 'Alice'
Test #6:
score: 0
Accepted
time: 4ms
memory: 4756kb
input:
MRCMABRQCQAB
output:
Alice
result:
ok single line: 'Alice'
Test #7:
score: 0
Accepted
time: 8ms
memory: 5076kb
input:
BBRCMMQAAQRC
output:
Alice
result:
ok single line: 'Alice'
Test #8:
score: 0
Accepted
time: 6ms
memory: 5220kb
input:
RRMCQMACABQB
output:
Alice
result:
ok single line: 'Alice'
Test #9:
score: 0
Accepted
time: 6ms
memory: 5380kb
input:
QMQBMRBACACR
output:
Alice
result:
ok single line: 'Alice'
Test #10:
score: 0
Accepted
time: 2ms
memory: 4368kb
input:
CMRQAQCBBRAM
output:
Alice
result:
ok single line: 'Alice'
Test #11:
score: 0
Accepted
time: 11ms
memory: 6248kb
input:
CABCRQMMRQAB
output:
Alice
result:
ok single line: 'Alice'
Test #12:
score: 0
Accepted
time: 27ms
memory: 9168kb
input:
ARCBBCMQRAQM
output:
Alice
result:
ok single line: 'Alice'
Test #13:
score: 0
Accepted
time: 1ms
memory: 4044kb
input:
ARCMCARMQBBQ
output:
Alice
result:
ok single line: 'Alice'
Test #14:
score: 0
Accepted
time: 16ms
memory: 7300kb
input:
AQABMCQCMRRB
output:
Bob
result:
ok single line: 'Bob'
Test #15:
score: 0
Accepted
time: 4ms
memory: 4504kb
input:
ACMRABRQMCBQ
output:
Alice
result:
ok single line: 'Alice'
Test #16:
score: 0
Accepted
time: 23ms
memory: 9096kb
input:
CBARMBCQMQAR
output:
Bob
result:
ok single line: 'Bob'
Test #17:
score: 0
Accepted
time: 27ms
memory: 9500kb
input:
RBABRQMCAMQC
output:
Bob
result:
ok single line: 'Bob'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
MBCQBQARRMCA
output:
Alice
result:
ok single line: 'Alice'
Test #19:
score: 0
Accepted
time: 14ms
memory: 6784kb
input:
AMBQRBCQACMR
output:
Bob
result:
ok single line: 'Bob'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
QRAMQMBBCRAC
output:
Alice
result:
ok single line: 'Alice'
Test #21:
score: 0
Accepted
time: 3ms
memory: 4252kb
input:
ARBCQMMBARQC
output:
Alice
result:
ok single line: 'Alice'
Test #22:
score: 0
Accepted
time: 38ms
memory: 15236kb
input:
CACAMBRQQRBM
output:
Bob
result:
ok single line: 'Bob'
Test #23:
score: 0
Accepted
time: 15ms
memory: 7380kb
input:
CQRRMMBQABCA
output:
Bob
result:
ok single line: 'Bob'
Test #24:
score: 0
Accepted
time: 9ms
memory: 6900kb
input:
ABABCQRMMCRQ
output:
Alice
result:
ok single line: 'Alice'
Test #25:
score: 0
Accepted
time: 8ms
memory: 5316kb
input:
CMBRAAQRQMBC
output:
Bob
result:
ok single line: 'Bob'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
AQBMRMQRBACC
output:
Alice
result:
ok single line: 'Alice'
Test #27:
score: 0
Accepted
time: 11ms
memory: 6236kb
input:
BRACQQMCAMBR
output:
Bob
result:
ok single line: 'Bob'
Test #28:
score: 0
Accepted
time: 4ms
memory: 4444kb
input:
MCCAQBMQRABR
output:
Bob
result:
ok single line: 'Bob'
Test #29:
score: 0
Accepted
time: 19ms
memory: 9228kb
input:
RBQBCRAACMQM
output:
Bob
result:
ok single line: 'Bob'
Test #30:
score: 0
Accepted
time: 7ms
memory: 5052kb
input:
ACRQARMBBQMC
output:
Bob
result:
ok single line: 'Bob'
Test #31:
score: 0
Accepted
time: 1ms
memory: 3876kb
input:
MRCQBCBQRMAA
output:
Alice
result:
ok single line: 'Alice'
Test #32:
score: 0
Accepted
time: 8ms
memory: 5292kb
input:
ACRQQCMMBBAR
output:
Bob
result:
ok single line: 'Bob'
Test #33:
score: 0
Accepted
time: 5ms
memory: 4740kb
input:
MMACQBRQABRC
output:
Bob
result:
ok single line: 'Bob'
Test #34:
score: 0
Accepted
time: 2ms
memory: 4040kb
input:
QACMQABRMCBR
output:
Alice
result:
ok single line: 'Alice'
Test #35:
score: 0
Accepted
time: 3ms
memory: 5192kb
input:
ACAQRCMRMBQB
output:
Alice
result:
ok single line: 'Alice'
Test #36:
score: 0
Accepted
time: 13ms
memory: 6260kb
input:
RABQCQMCABMR
output:
Bob
result:
ok single line: 'Bob'
Test #37:
score: 0
Accepted
time: 6ms
memory: 4808kb
input:
QQBARCRBMMAC
output:
Alice
result:
ok single line: 'Alice'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
RQMRQABCABCM
output:
Alice
result:
ok single line: 'Alice'
Test #39:
score: 0
Accepted
time: 3ms
memory: 4228kb
input:
RQAMBRQCCBMA
output:
Alice
result:
ok single line: 'Alice'
Test #40:
score: 0
Accepted
time: 2ms
memory: 3824kb
input:
QQBACMARMRBC
output:
Alice
result:
ok single line: 'Alice'
Test #41:
score: 0
Accepted
time: 7ms
memory: 5180kb
input:
QAQCRRAMMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #42:
score: 0
Accepted
time: 6ms
memory: 5016kb
input:
QQBMCBRARMAC
output:
Bob
result:
ok single line: 'Bob'
Test #43:
score: 0
Accepted
time: 45ms
memory: 15340kb
input:
BABARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #44:
score: 0
Accepted
time: 258ms
memory: 53616kb
input:
BBARARCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #45:
score: 0
Accepted
time: 29ms
memory: 9648kb
input:
BBAARCRCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #46:
score: 0
Accepted
time: 76ms
memory: 19324kb
input:
BBAARRCQCQMM
output:
Bob
result:
ok single line: 'Bob'
Test #47:
score: 0
Accepted
time: 60ms
memory: 16576kb
input:
BBAARRCCQMQM
output:
Bob
result:
ok single line: 'Bob'
Test #48:
score: 0
Accepted
time: 191ms
memory: 37608kb
input:
BBAACCRQMQRM
output:
Bob
result:
ok single line: 'Bob'
Test #49:
score: 0
Accepted
time: 271ms
memory: 53540kb
input:
BACBACQRRQMM
output:
Bob
result:
ok single line: 'Bob'
Test #50:
score: 0
Accepted
time: 770ms
memory: 107812kb
input:
RAABBRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #51:
score: 0
Accepted
time: 40ms
memory: 11584kb
input:
RABRBQMCACQM
output:
Bob
result:
ok single line: 'Bob'
Test #52:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
CMMQQABCRABR
output:
Alice
result:
ok single line: 'Alice'
Test #53:
score: 0
Accepted
time: 97ms
memory: 28068kb
input:
RBAABRCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Extra Test:
score: 0
Extra Test Passed