QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#230299 | #7635. Fairy Chess | ucup-team1191# | AC ✓ | 1224ms | 112448kb | C++23 | 5.1kb | 2023-10-28 18:02:15 | 2023-10-28 18:02:16 |
Judging History
answer
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
enum class Piece {
BISHOP,
ROOK,
QUEEN,
ARCHBISHOP,
CHANCELLOR,
MAHARAJAH,
KNIGHT,
};
const int N = 8;
const int K = 6;
ull mask_cover[N][N][K + 1];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
auto valid = [&](int x, int y) { return 0 <= x && x < N && 0 <= y && y < N; };
auto add = [&](int i, int j, int x, int y, Piece k) {
if (valid(x, y)) {
mask_cover[i][j][(int)k] |= 1ULL << (x * N + y);
}
};
{ // knight
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
add(i, j, i, j, Piece::KNIGHT);
add(i, j, i + 1, j + 2, Piece::KNIGHT);
add(i, j, i + 1, j - 2, Piece::KNIGHT);
add(i, j, i - 1, j + 2, Piece::KNIGHT);
add(i, j, i - 1, j - 2, Piece::KNIGHT);
add(i, j, i + 2, j + 1, Piece::KNIGHT);
add(i, j, i + 2, j - 1, Piece::KNIGHT);
add(i, j, i - 2, j + 1, Piece::KNIGHT);
add(i, j, i - 2, j - 1, Piece::KNIGHT);
}
}
}
{ // bishop
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
for (int t = 0; t < 3 * N; ++t) {
add(i, j, i + t, j + t, Piece::BISHOP);
add(i, j, i + t, j - t, Piece::BISHOP);
add(i, j, i - t, j + t, Piece::BISHOP);
add(i, j, i - t, j - t, Piece::BISHOP);
}
}
}
}
{ // rook
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
for (int t = 0; t < 3 * N; ++t) {
add(i, j, i + t, j, Piece::ROOK);
add(i, j, i - t, j, Piece::ROOK);
add(i, j, i, j + t, Piece::ROOK);
add(i, j, i, j - t, Piece::ROOK);
}
}
}
}
{ // queen
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
mask_cover[i][j][(int)Piece::QUEEN] =
mask_cover[i][j][(int)Piece::BISHOP] |
mask_cover[i][j][(int)Piece::ROOK];
}
}
}
{ // archibishop
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
mask_cover[i][j][(int)Piece::ARCHBISHOP] =
mask_cover[i][j][(int)Piece::BISHOP] |
mask_cover[i][j][(int)Piece::KNIGHT];
}
}
}
{ // chancellor
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
mask_cover[i][j][(int)Piece::CHANCELLOR] =
mask_cover[i][j][(int)Piece::ROOK] |
mask_cover[i][j][(int)Piece::KNIGHT];
}
}
}
{ // maharajah
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
mask_cover[i][j][(int)Piece::MAHARAJAH] =
mask_cover[i][j][(int)Piece::QUEEN] |
mask_cover[i][j][(int)Piece::KNIGHT];
}
}
}
vector<int> order(2 * K);
for (int i = 0; i < 2 * K; ++i) {
char c;
cin >> c;
if (c == 'B') {
order[i] = (int)Piece::BISHOP;
} else if (c == 'R') {
order[i] = (int)Piece::ROOK;
} else if (c == 'Q') {
order[i] = (int)Piece::QUEEN;
} else if (c == 'A') {
order[i] = (int)Piece::ARCHBISHOP;
} else if (c == 'C') {
order[i] = (int)Piece::CHANCELLOR;
} else if (c == 'M') {
order[i] = (int)Piece::MAHARAJAH;
} else {
assert(false);
}
}
/*for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cout << ((mask_cover[3][3][(int)Piece::MAHARAJAH] >> (N * i + j)) & 1);
}
cout << '\n';
}
return 0;*/
mt19937_64 rnd(123);
ull mask_pieces = 0;
ull mask_covered = 0;
int ptr = 0;
map<pair<ull, ull>, bool> mem;
function<bool()> rec = [&]() {
auto hash_pos = make_pair(mask_covered, mask_pieces);
if (mem.count(hash_pos)) {
return mem[hash_pos];
}
if (ptr == 2 * K) {
mem[hash_pos] = false;
return false;
}
ull mask_covered_anti = ~mask_covered;
while (mask_covered_anti > 0) {
int b = __builtin_ctzll(mask_covered_anti);
mask_covered_anti &= ~(1ULL << b);
int i = b / N;
int j = b % N;
int p = order[ptr];
if (mask_pieces & mask_cover[i][j][p]) {
continue;
}
ull sf_covered = mask_covered;
mask_pieces |= (1ULL << (i * N + j));
mask_covered |= mask_cover[i][j][p];
++ptr;
auto res = rec();
--ptr;
mask_pieces &= ~(1ULL << (i * N + j));
mask_covered = sf_covered;
if (!res) {
mem[hash_pos] = true;
return true;
}
}
mem[hash_pos] = false;
return false;
};
cout << (rec() ? "Alice" : "Bob") << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 112ms
memory: 17580kb
input:
BBAARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 6ms
memory: 4492kb
input:
BAMBAMQQRCCR
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: 0
Accepted
time: 3ms
memory: 3968kb
input:
QQRAACMRMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #4:
score: 0
Accepted
time: 10ms
memory: 5356kb
input:
MBBARQRMACQC
output:
Alice
result:
ok single line: 'Alice'
Test #5:
score: 0
Accepted
time: 3ms
memory: 3960kb
input:
ACQCMQRBBRMA
output:
Alice
result:
ok single line: 'Alice'
Test #6:
score: 0
Accepted
time: 7ms
memory: 4732kb
input:
MRCMABRQCQAB
output:
Alice
result:
ok single line: 'Alice'
Test #7:
score: 0
Accepted
time: 16ms
memory: 5496kb
input:
BBRCMMQAAQRC
output:
Alice
result:
ok single line: 'Alice'
Test #8:
score: 0
Accepted
time: 11ms
memory: 5352kb
input:
RRMCQMACABQB
output:
Alice
result:
ok single line: 'Alice'
Test #9:
score: 0
Accepted
time: 12ms
memory: 5476kb
input:
QMQBMRBACACR
output:
Alice
result:
ok single line: 'Alice'
Test #10:
score: 0
Accepted
time: 3ms
memory: 4536kb
input:
CMRQAQCBBRAM
output:
Alice
result:
ok single line: 'Alice'
Test #11:
score: 0
Accepted
time: 15ms
memory: 6068kb
input:
CABCRQMMRQAB
output:
Alice
result:
ok single line: 'Alice'
Test #12:
score: 0
Accepted
time: 30ms
memory: 9640kb
input:
ARCBBCMQRAQM
output:
Alice
result:
ok single line: 'Alice'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
ARCMCARMQBBQ
output:
Alice
result:
ok single line: 'Alice'
Test #14:
score: 0
Accepted
time: 27ms
memory: 7864kb
input:
AQABMCQCMRRB
output:
Bob
result:
ok single line: 'Bob'
Test #15:
score: 0
Accepted
time: 0ms
memory: 4604kb
input:
ACMRABRQMCBQ
output:
Alice
result:
ok single line: 'Alice'
Test #16:
score: 0
Accepted
time: 32ms
memory: 9144kb
input:
CBARMBCQMQAR
output:
Bob
result:
ok single line: 'Bob'
Test #17:
score: 0
Accepted
time: 41ms
memory: 9840kb
input:
RBABRQMCAMQC
output:
Bob
result:
ok single line: 'Bob'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
MBCQBQARRMCA
output:
Alice
result:
ok single line: 'Alice'
Test #19:
score: 0
Accepted
time: 14ms
memory: 7224kb
input:
AMBQRBCQACMR
output:
Bob
result:
ok single line: 'Bob'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
QRAMQMBBCRAC
output:
Alice
result:
ok single line: 'Alice'
Test #21:
score: 0
Accepted
time: 4ms
memory: 4216kb
input:
ARBCQMMBARQC
output:
Alice
result:
ok single line: 'Alice'
Test #22:
score: 0
Accepted
time: 70ms
memory: 14348kb
input:
CACAMBRQQRBM
output:
Bob
result:
ok single line: 'Bob'
Test #23:
score: 0
Accepted
time: 30ms
memory: 7812kb
input:
CQRRMMBQABCA
output:
Bob
result:
ok single line: 'Bob'
Test #24:
score: 0
Accepted
time: 15ms
memory: 7228kb
input:
ABABCQRMMCRQ
output:
Alice
result:
ok single line: 'Alice'
Test #25:
score: 0
Accepted
time: 13ms
memory: 5812kb
input:
CMBRAAQRQMBC
output:
Bob
result:
ok single line: 'Bob'
Test #26:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
AQBMRMQRBACC
output:
Alice
result:
ok single line: 'Alice'
Test #27:
score: 0
Accepted
time: 14ms
memory: 6372kb
input:
BRACQQMCAMBR
output:
Bob
result:
ok single line: 'Bob'
Test #28:
score: 0
Accepted
time: 5ms
memory: 4504kb
input:
MCCAQBMQRABR
output:
Bob
result:
ok single line: 'Bob'
Test #29:
score: 0
Accepted
time: 33ms
memory: 9260kb
input:
RBQBCRAACMQM
output:
Bob
result:
ok single line: 'Bob'
Test #30:
score: 0
Accepted
time: 11ms
memory: 5516kb
input:
ACRQARMBBQMC
output:
Bob
result:
ok single line: 'Bob'
Test #31:
score: 0
Accepted
time: 2ms
memory: 3760kb
input:
MRCQBCBQRMAA
output:
Alice
result:
ok single line: 'Alice'
Test #32:
score: 0
Accepted
time: 8ms
memory: 5696kb
input:
ACRQQCMMBBAR
output:
Bob
result:
ok single line: 'Bob'
Test #33:
score: 0
Accepted
time: 8ms
memory: 4976kb
input:
MMACQBRQABRC
output:
Bob
result:
ok single line: 'Bob'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
QACMQABRMCBR
output:
Alice
result:
ok single line: 'Alice'
Test #35:
score: 0
Accepted
time: 11ms
memory: 5484kb
input:
ACAQRCMRMBQB
output:
Alice
result:
ok single line: 'Alice'
Test #36:
score: 0
Accepted
time: 18ms
memory: 6632kb
input:
RABQCQMCABMR
output:
Bob
result:
ok single line: 'Bob'
Test #37:
score: 0
Accepted
time: 9ms
memory: 5024kb
input:
QQBARCRBMMAC
output:
Alice
result:
ok single line: 'Alice'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
RQMRQABCABCM
output:
Alice
result:
ok single line: 'Alice'
Test #39:
score: 0
Accepted
time: 4ms
memory: 4252kb
input:
RQAMBRQCCBMA
output:
Alice
result:
ok single line: 'Alice'
Test #40:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
QQBACMARMRBC
output:
Alice
result:
ok single line: 'Alice'
Test #41:
score: 0
Accepted
time: 12ms
memory: 5624kb
input:
QAQCRRAMMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #42:
score: 0
Accepted
time: 11ms
memory: 5276kb
input:
QQBMCBRARMAC
output:
Bob
result:
ok single line: 'Bob'
Test #43:
score: 0
Accepted
time: 88ms
memory: 14636kb
input:
BABARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #44:
score: 0
Accepted
time: 517ms
memory: 51496kb
input:
BBARARCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #45:
score: 0
Accepted
time: 45ms
memory: 10132kb
input:
BBAARCRCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #46:
score: 0
Accepted
time: 146ms
memory: 21420kb
input:
BBAARRCQCQMM
output:
Bob
result:
ok single line: 'Bob'
Test #47:
score: 0
Accepted
time: 104ms
memory: 17608kb
input:
BBAARRCCQMQM
output:
Bob
result:
ok single line: 'Bob'
Test #48:
score: 0
Accepted
time: 356ms
memory: 41768kb
input:
BBAACCRQMQRM
output:
Bob
result:
ok single line: 'Bob'
Test #49:
score: 0
Accepted
time: 482ms
memory: 54624kb
input:
BACBACQRRQMM
output:
Bob
result:
ok single line: 'Bob'
Test #50:
score: 0
Accepted
time: 1224ms
memory: 112448kb
input:
RAABBRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #51:
score: 0
Accepted
time: 54ms
memory: 12584kb
input:
RABRBQMCACQM
output:
Bob
result:
ok single line: 'Bob'
Test #52:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
CMMQQABCRABR
output:
Alice
result:
ok single line: 'Alice'
Test #53:
score: 0
Accepted
time: 205ms
memory: 27228kb
input:
RBAABRCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Extra Test:
score: 0
Extra Test Passed