QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#231926 | #7635. Fairy Chess | tselmegkh# | WA | 186ms | 14248kb | C++14 | 4.1kb | 2023-10-29 18:09:22 | 2023-10-29 18:09:23 |
Judging History
answer
#include <iostream>
#include <vector>
#include <cstring>
#include <array>
#include <map>
#include <unordered_map>
#include <algorithm>
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<unordered_map<ull, int>> w(12);
int cnt(ull n) {
int a = 0;
while (n) {
a += n % 2;
n /= 2;
}
return a;
}
int rec(int i, ull a) {
if (i == s.size()) {
return 0;
}
if (w[i].find(a) != w[i].end()) {
return w[i][a];
}
vector<pair<int, ull>> v;
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 >> (8 * x + y) & 1) == 0) {
v.push_back({cnt((a | b) - a), a | b});
}
}
}
sort(v.rbegin(), v.rend());
for (int j = 0; j < v.size() && j < 400; j++) {
if (!rec(i + 1, v[j].second)) return w[i][a] = 1;
}
// for (int j = 0; j < v.size() && j < 150; j++) {
// if (!rec(i + 1, v[(int)v.size() - 1 - j].second)) 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;
for (int i = 0; i < 4; i++) {
for (int j = i; j < 4; j++) {
if (!rec(1, T[t[s[0] - 'A']][8 * i + j])) {
cout << "Alice";
return 0;
}
}
}
cout << "Bob";
// cout << (rec(0, 0) ? "Alice" : "Bob");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 75ms
memory: 8800kb
input:
BBAARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 186ms
memory: 14248kb
input:
BAMBAMQQRCCR
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: -100
Wrong Answer
time: 61ms
memory: 6524kb
input:
QQRAACMRMCBB
output:
Bob
result:
wrong answer 1st lines differ - expected: 'Alice', found: 'Bob'