QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#594062 | #7635. Fairy Chess | ucup-team3519# | AC ✓ | 147ms | 3844kb | C++17 | 4.1kb | 2024-09-27 18:40:56 | 2024-09-27 18:40:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define V vector
#define pb push_back
void apply_sig(ULL &bit, int x, int y) {
if(x >= 0 && y >= 0 && x <= 7 && y <= 7) bit |= 1ULL << (x + y * 8);
}
void show(ULL x) {
for(int i = 0; i < 8; i++) {
for(int j = 0; j < 8; j++) {
cout << (x >> (j * 8 + i) & 1);
}
cout << endl;
}
}
ULL apply(ULL bit, int id, char c) {
int x = id % 8, y = id / 8;
// cout << "apply : " << c << " on : " << x << " " << y << endl;
// show(bit);
if(c == 'R' || c == 'Q' || c == 'M' || c == 'C') {//ju
for(int i = 0; i < 8; i++) {
apply_sig(bit, x, i);
apply_sig(bit, i, y);
}
}
if(c == 'Q' || c == 'M' || c == 'B' || c == 'A') {//xiang
int n_x = x, n_y = y;
while(n_x && n_y) n_x--, n_y--;
while(n_x < 8 && n_y < 8) apply_sig(bit, n_x, n_y), n_x++, n_y++;
n_x = x, n_y = y;
while(n_x != 0 && n_y != 7) n_x--, n_y++;
while(n_x < 8 && n_y >= 0) {
apply_sig(bit, n_x, n_y), n_x++, n_y--;
}
}
if(c == 'A' || c == 'C' || c == 'M') {
apply_sig(bit, x - 2, y - 1);
apply_sig(bit, x - 1, y - 2);
apply_sig(bit, x - 2, y + 1);
apply_sig(bit, x - 1, y + 2);
apply_sig(bit, x + 2, y - 1);
apply_sig(bit, x + 1, y - 2);
apply_sig(bit, x + 2, y + 1);
apply_sig(bit, x + 1, y + 2);
}
// cout << "output : " << bit << endl;
// show(bit);
// system("pause");
return bit;
}
int main() {
string s; cin >> s;
map<pair<int, ULL>, bool> mp;
V<V<ULL>> store(64, V<ULL>(26));
for(int i = 0; i < 64; i++) {
store[i]['A' - 'A'] = apply(0, i, 'A');
store[i]['C' - 'A'] = apply(0, i, 'C');
store[i]['M' - 'A'] = apply(0, i, 'M');
store[i]['B' - 'A'] = apply(0, i, 'B');
store[i]['R' - 'A'] = apply(0, i, 'R');
store[i]['Q' - 'A'] = apply(0, i, 'Q');
// if(i == 12) {
// cout << " i : " << i << endl;
// cout << " c : " << 'A' << endl;
// show(store[i]['A' - 'A']);
// cout << " i : " << i << endl;
// cout << " c : " << 'C' << endl;
// show(store[i]['C' - 'A']);
// cout << " i : " << i << endl;
// cout << " c : " << 'M' << endl;
// show(store[i]['M' - 'A']);
// cout << " i : " << i << endl;
// cout << " c : " << 'R' << endl;
// show(store[i]['R' - 'A']);
// cout << " i : " << i << endl;
// cout << " c : " << 'Q' << endl;
// show(store[i]['Q' - 'A']);
// cout << " i : " << i << endl;
// cout << " c : " << 'B' << endl;
// show(store[i]['B' - 'A']);
// }
}
auto better_apply = [&](ULL board, int pos, char c) {
ULL ans = board | store[pos][c - 'A'];
// assert(ans == apply(board, pos, c));
return ans;
};
auto id = [&](int x, int y) -> int {
return y * 8 + x;
};
// int time = 0;
auto dfs = [&](int pos, ULL board, ULL chess, auto dfs) -> bool {
// time++;
// if(time % 10000000 == 0) cout << time << endl;
if(board == ~0ULL) return 0;
assert(pos < 12);
bool ok = 0;
ULL find_board = ~board;
while(find_board) {
int i = __lg(find_board);
find_board ^= 1ULL << i;
assert(!(board >> i & 1));
ULL n_board = better_apply(board, i, s[pos]);
if(better_apply(0, i, s[pos]) & chess) continue;
ULL n_chess = chess | (1ULL << i);
if(!dfs(pos + 1, n_board, n_chess, dfs)) {
ok = 1;
break;
}
}
// return mp[{pos, board}] = ok;
return ok;
};
auto alice = dfs(0, 0, 0, dfs);
cout << (alice ? "Alice" : "Bob") << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 16ms
memory: 3764kb
input:
BBAARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
BAMBAMQQRCCR
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
QQRAACMRMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3844kb
input:
MBBARQRMACQC
output:
Alice
result:
ok single line: 'Alice'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
ACQCMQRBBRMA
output:
Alice
result:
ok single line: 'Alice'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
MRCMABRQCQAB
output:
Alice
result:
ok single line: 'Alice'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
BBRCMMQAAQRC
output:
Alice
result:
ok single line: 'Alice'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
RRMCQMACABQB
output:
Alice
result:
ok single line: 'Alice'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
QMQBMRBACACR
output:
Alice
result:
ok single line: 'Alice'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
CMRQAQCBBRAM
output:
Alice
result:
ok single line: 'Alice'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
CABCRQMMRQAB
output:
Alice
result:
ok single line: 'Alice'
Test #12:
score: 0
Accepted
time: 6ms
memory: 3832kb
input:
ARCBBCMQRAQM
output:
Alice
result:
ok single line: 'Alice'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
ARCMCARMQBBQ
output:
Alice
result:
ok single line: 'Alice'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
AQABMCQCMRRB
output:
Bob
result:
ok single line: 'Bob'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
ACMRABRQMCBQ
output:
Alice
result:
ok single line: 'Alice'
Test #16:
score: 0
Accepted
time: 4ms
memory: 3552kb
input:
CBARMBCQMQAR
output:
Bob
result:
ok single line: 'Bob'
Test #17:
score: 0
Accepted
time: 6ms
memory: 3772kb
input:
RBABRQMCAMQC
output:
Bob
result:
ok single line: 'Bob'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
MBCQBQARRMCA
output:
Alice
result:
ok single line: 'Alice'
Test #19:
score: 0
Accepted
time: 3ms
memory: 3616kb
input:
AMBQRBCQACMR
output:
Bob
result:
ok single line: 'Bob'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
QRAMQMBBCRAC
output:
Alice
result:
ok single line: 'Alice'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
ARBCQMMBARQC
output:
Alice
result:
ok single line: 'Alice'
Test #22:
score: 0
Accepted
time: 9ms
memory: 3768kb
input:
CACAMBRQQRBM
output:
Bob
result:
ok single line: 'Bob'
Test #23:
score: 0
Accepted
time: 3ms
memory: 3624kb
input:
CQRRMMBQABCA
output:
Bob
result:
ok single line: 'Bob'
Test #24:
score: 0
Accepted
time: 4ms
memory: 3556kb
input:
ABABCQRMMCRQ
output:
Alice
result:
ok single line: 'Alice'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
CMBRAAQRQMBC
output:
Bob
result:
ok single line: 'Bob'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
AQBMRMQRBACC
output:
Alice
result:
ok single line: 'Alice'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3612kb
input:
BRACQQMCAMBR
output:
Bob
result:
ok single line: 'Bob'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
MCCAQBMQRABR
output:
Bob
result:
ok single line: 'Bob'
Test #29:
score: 0
Accepted
time: 4ms
memory: 3616kb
input:
RBQBCRAACMQM
output:
Bob
result:
ok single line: 'Bob'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
ACRQARMBBQMC
output:
Bob
result:
ok single line: 'Bob'
Test #31:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
MRCQBCBQRMAA
output:
Alice
result:
ok single line: 'Alice'
Test #32:
score: 0
Accepted
time: 2ms
memory: 3616kb
input:
ACRQQCMMBBAR
output:
Bob
result:
ok single line: 'Bob'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
MMACQBRQABRC
output:
Bob
result:
ok single line: 'Bob'
Test #34:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
QACMQABRMCBR
output:
Alice
result:
ok single line: 'Alice'
Test #35:
score: 0
Accepted
time: 2ms
memory: 3760kb
input:
ACAQRCMRMBQB
output:
Alice
result:
ok single line: 'Alice'
Test #36:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
RABQCQMCABMR
output:
Bob
result:
ok single line: 'Bob'
Test #37:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
QQBARCRBMMAC
output:
Alice
result:
ok single line: 'Alice'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
RQMRQABCABCM
output:
Alice
result:
ok single line: 'Alice'
Test #39:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
RQAMBRQCCBMA
output:
Alice
result:
ok single line: 'Alice'
Test #40:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
QQBACMARMRBC
output:
Alice
result:
ok single line: 'Alice'
Test #41:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
QAQCRRAMMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #42:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
QQBMCBRARMAC
output:
Bob
result:
ok single line: 'Bob'
Test #43:
score: 0
Accepted
time: 17ms
memory: 3840kb
input:
BABARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #44:
score: 0
Accepted
time: 85ms
memory: 3616kb
input:
BBARARCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #45:
score: 0
Accepted
time: 8ms
memory: 3660kb
input:
BBAARCRCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #46:
score: 0
Accepted
time: 23ms
memory: 3596kb
input:
BBAARRCQCQMM
output:
Bob
result:
ok single line: 'Bob'
Test #47:
score: 0
Accepted
time: 16ms
memory: 3616kb
input:
BBAARRCCQMQM
output:
Bob
result:
ok single line: 'Bob'
Test #48:
score: 0
Accepted
time: 42ms
memory: 3504kb
input:
BBAACCRQMQRM
output:
Bob
result:
ok single line: 'Bob'
Test #49:
score: 0
Accepted
time: 41ms
memory: 3556kb
input:
BACBACQRRQMM
output:
Bob
result:
ok single line: 'Bob'
Test #50:
score: 0
Accepted
time: 147ms
memory: 3552kb
input:
RAABBRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #51:
score: 0
Accepted
time: 10ms
memory: 3844kb
input:
RABRBQMCACQM
output:
Bob
result:
ok single line: 'Bob'
Test #52:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
CMMQQABCRABR
output:
Alice
result:
ok single line: 'Alice'
Test #53:
score: 0
Accepted
time: 27ms
memory: 3628kb
input:
RBAABRCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Extra Test:
score: 0
Extra Test Passed