QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#231875 | #7635. Fairy Chess | tselmegkh# | WA | 0ms | 3816kb | C++14 | 3.4kb | 2023-10-29 17:30:07 | 2023-10-29 17:30:09 |
Judging History
answer
#include <iostream>
#include <vector>
#include <cstring>
#include <array>
#include <map>
using namespace std;
using ll = long long;
using ull = unsigned long long;
string s;
ull B[64], R[64], K[64], Q[64], A[64], C[64], M[64], T[6][64];
vector<int> t(26);
vector<map<ull, int>> w(12);
int rec(int i, ull a) {
if (i == s.size()) {
return 0;
}
if (w[i].find(a) != w[i].end()) {
return w[i][a];
}
for (int x = 0; x < 8; x++) {
for (int y = 0; y < 8; y++) {
ull b = T[t[s[i] - 'A']][8 * x + y];
if ((a & b) == 0) {
if (!rec(i + 1, a + b)) return w[i][a] = 1;
}
}
}
return w[i][a] = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
ull s = 0; int x, y;
x = i, y = j;
while (x >= 0 && y >= 0) {
s += 1ULL << (8 * x + y);
x--, y--;
}
x = i, y = j;
while (x >= 0 && y < 8) {
s += 1ULL << (8 * x + y);
x--, y++;
}
x = i, y = j;
while (x < 8 && y >= 0) {
s += 1ULL << (8 * x + y);
x++, y--;
}
x = i, y = j;
while (x < 8 && y < 8) {
s += 1ULL << (8 * x + y);
x++, y++;
}
B[8 * i + j] = s;
}
}
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
ull s = 0; int x, y;
x = i, y = j;
while (x >= 0) {
s += 1ULL << (8 * x + y);
x--;
}
x = i, y = j;
while (x < 8) {
s += 1ULL << (8 * x + y);
x++;
}
x = i, y = j;
while (y >= 0) {
s += 1ULL << (8 * x + y);
y--;
}
x = i, y = j;
while (y < 8) {
s += 1ULL << (8 * x + y);
y++;
}
R[8 * i + j] = s;
}
}
vector<pair<int, int>> p;
p.emplace_back(0, 0);
p.emplace_back(-2, -1);
p.emplace_back(-2, 1);
p.emplace_back(-1, 2);
p.emplace_back(1, 2);
p.emplace_back(2, 1);
p.emplace_back(2, -1);
p.emplace_back(1, -2);
p.emplace_back(-1, -2);
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
ull s = 0; int x, y;
for (auto [dx, dy] : p) {
x = i + dx;
y = j + dy;
if (x >= 0 && y >= 0 && x < 8 && y < 8) {
s += 1ULL << (8 * x + y);
}
}
K[8 * i + j] = s;
}
}
for (int i = 0; i < 64; i++) {
Q[i] = R[i] | B[i];
A[i] = B[i] | K[i];
C[i] = R[i] | K[i];
M[i] = Q[i] | K[i];
T[0][i] = B[i];
T[1][i] = R[i];
T[2][i] = Q[i];
T[3][i] = A[i];
T[4][i] = C[i];
T[5][i] = M[i];
}
t['B' - 'A'] = 0;
t['R' - 'A'] = 1;
t['Q' - 'A'] = 2;
t['A' - 'A'] = 3;
t['C' - 'A'] = 4;
t['M' - 'A'] = 5;
cin >> s;
cout << (rec(0, 0) ? "Alice" : "Bob");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
BBAARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
BAMBAMQQRCCR
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
QQRAACMRMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
MBBARQRMACQC
output:
Alice
result:
ok single line: 'Alice'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
ACQCMQRBBRMA
output:
Alice
result:
ok single line: 'Alice'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
MRCMABRQCQAB
output:
Alice
result:
ok single line: 'Alice'
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 3552kb
input:
BBRCMMQAAQRC
output:
Bob
result:
wrong answer 1st lines differ - expected: 'Alice', found: 'Bob'