QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#229024 | #7635. Fairy Chess | ucup-team022# | AC ✓ | 1706ms | 3808kb | C++17 | 1.7kb | 2023-10-28 14:50:46 | 2023-10-28 14:50:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e9, n = 8;
typedef pair<int, int> pr;
string str;
int t[10][10], has[10][10];
// t: 之前能攻击到的
// has: 之前有的
vector<pr> V = {pr(-1, -2), pr(-1, 2), pr(1, 2), pr(1, -2),
pr(2, 1), pr(2, -1), pr(-2, 1), pr(-2, -1)};
bool Put(char ch, int x, int y) {
int at[10][10];
memcpy(at, t, sizeof(t));
if (ch == 'B' || ch == 'A' || ch == 'Q' || ch == 'M') {
for (int i = -1; i <= 1; i += 2) {
for (int j = -1; j <= 1; j += 2) {
int tx = x, ty = y;
while (tx >= 1 && tx <= n && ty >= 1 && ty <= n) {
if (has[tx][ty]) return 0;
at[tx][ty]++;
tx += i, ty += j;
}
}
}
}
if (ch == 'R' || ch == 'C' || ch == 'Q' || ch == 'M') {
for (int i = -1; i <= 1; i += 2) {
for (int j = -1; j <= 1; j += 2) {
int tx = x, ty = y;
while (tx >= 1 && tx <= n && ty >= 1 && ty <= n) {
if (has[tx][ty]) return 0;
at[tx][ty]++;
tx += (i + j) / 2, ty += (i - j) / 2;
}
}
}
}
if (ch == 'A' || ch == 'C' || ch == 'M') {
for (auto [i, j] : V) {
int tx = x + i, ty = y + j;
if (tx >= 1 && tx <= n && ty >= 1 && ty <= n) {
if (has[tx][ty]) return 0;
at[tx][ty]++;
}
}
}
memcpy(t, at, sizeof(t));
return 1;
}
bool dfs(int x) {
for (int i = 1; i <= 8; i++) {
for (int j = 1; j <= 8; j++) {
if (t[i][j]) continue;
int tt[10][10];
memcpy(tt, t, sizeof(t));
if (Put(str[x], i, j)) {
has[i][j] = 1;
if (!dfs(x + 1)) {
memcpy(t, tt, sizeof(t));
has[i][j] = 0;
return 1;
}
has[i][j] = 0;
memcpy(t, tt, sizeof(t));
}
}
}
return 0;
}
int main() {
cin >> str;
cout << (dfs(0) ? "Alice" : "Bob");
}
詳細信息
Test #1:
score: 100
Accepted
time: 167ms
memory: 3540kb
input:
BBAARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 9ms
memory: 3808kb
input:
BAMBAMQQRCCR
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: 0
Accepted
time: 4ms
memory: 3576kb
input:
QQRAACMRMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #4:
score: 0
Accepted
time: 19ms
memory: 3808kb
input:
MBBARQRMACQC
output:
Alice
result:
ok single line: 'Alice'
Test #5:
score: 0
Accepted
time: 4ms
memory: 3680kb
input:
ACQCMQRBBRMA
output:
Alice
result:
ok single line: 'Alice'
Test #6:
score: 0
Accepted
time: 6ms
memory: 3600kb
input:
MRCMABRQCQAB
output:
Alice
result:
ok single line: 'Alice'
Test #7:
score: 0
Accepted
time: 20ms
memory: 3540kb
input:
BBRCMMQAAQRC
output:
Alice
result:
ok single line: 'Alice'
Test #8:
score: 0
Accepted
time: 11ms
memory: 3508kb
input:
RRMCQMACABQB
output:
Alice
result:
ok single line: 'Alice'
Test #9:
score: 0
Accepted
time: 9ms
memory: 3516kb
input:
QMQBMRBACACR
output:
Alice
result:
ok single line: 'Alice'
Test #10:
score: 0
Accepted
time: 3ms
memory: 3592kb
input:
CMRQAQCBBRAM
output:
Alice
result:
ok single line: 'Alice'
Test #11:
score: 0
Accepted
time: 23ms
memory: 3592kb
input:
CABCRQMMRQAB
output:
Alice
result:
ok single line: 'Alice'
Test #12:
score: 0
Accepted
time: 66ms
memory: 3464kb
input:
ARCBBCMQRAQM
output:
Alice
result:
ok single line: 'Alice'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
ARCMCARMQBBQ
output:
Alice
result:
ok single line: 'Alice'
Test #14:
score: 0
Accepted
time: 42ms
memory: 3600kb
input:
AQABMCQCMRRB
output:
Bob
result:
ok single line: 'Bob'
Test #15:
score: 0
Accepted
time: 8ms
memory: 3512kb
input:
ACMRABRQMCBQ
output:
Alice
result:
ok single line: 'Alice'
Test #16:
score: 0
Accepted
time: 42ms
memory: 3804kb
input:
CBARMBCQMQAR
output:
Bob
result:
ok single line: 'Bob'
Test #17:
score: 0
Accepted
time: 71ms
memory: 3600kb
input:
RBABRQMCAMQC
output:
Bob
result:
ok single line: 'Bob'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
MBCQBQARRMCA
output:
Alice
result:
ok single line: 'Alice'
Test #19:
score: 0
Accepted
time: 22ms
memory: 3508kb
input:
AMBQRBCQACMR
output:
Bob
result:
ok single line: 'Bob'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
QRAMQMBBCRAC
output:
Alice
result:
ok single line: 'Alice'
Test #21:
score: 0
Accepted
time: 8ms
memory: 3808kb
input:
ARBCQMMBARQC
output:
Alice
result:
ok single line: 'Alice'
Test #22:
score: 0
Accepted
time: 94ms
memory: 3808kb
input:
CACAMBRQQRBM
output:
Bob
result:
ok single line: 'Bob'
Test #23:
score: 0
Accepted
time: 28ms
memory: 3536kb
input:
CQRRMMBQABCA
output:
Bob
result:
ok single line: 'Bob'
Test #24:
score: 0
Accepted
time: 49ms
memory: 3600kb
input:
ABABCQRMMCRQ
output:
Alice
result:
ok single line: 'Alice'
Test #25:
score: 0
Accepted
time: 17ms
memory: 3460kb
input:
CMBRAAQRQMBC
output:
Bob
result:
ok single line: 'Bob'
Test #26:
score: 0
Accepted
time: 3ms
memory: 3588kb
input:
AQBMRMQRBACC
output:
Alice
result:
ok single line: 'Alice'
Test #27:
score: 0
Accepted
time: 25ms
memory: 3804kb
input:
BRACQQMCAMBR
output:
Bob
result:
ok single line: 'Bob'
Test #28:
score: 0
Accepted
time: 5ms
memory: 3800kb
input:
MCCAQBMQRABR
output:
Bob
result:
ok single line: 'Bob'
Test #29:
score: 0
Accepted
time: 41ms
memory: 3536kb
input:
RBQBCRAACMQM
output:
Bob
result:
ok single line: 'Bob'
Test #30:
score: 0
Accepted
time: 16ms
memory: 3516kb
input:
ACRQARMBBQMC
output:
Bob
result:
ok single line: 'Bob'
Test #31:
score: 0
Accepted
time: 2ms
memory: 3508kb
input:
MRCQBCBQRMAA
output:
Alice
result:
ok single line: 'Alice'
Test #32:
score: 0
Accepted
time: 12ms
memory: 3576kb
input:
ACRQQCMMBBAR
output:
Bob
result:
ok single line: 'Bob'
Test #33:
score: 0
Accepted
time: 7ms
memory: 3732kb
input:
MMACQBRQABRC
output:
Bob
result:
ok single line: 'Bob'
Test #34:
score: 0
Accepted
time: 2ms
memory: 3588kb
input:
QACMQABRMCBR
output:
Alice
result:
ok single line: 'Alice'
Test #35:
score: 0
Accepted
time: 16ms
memory: 3736kb
input:
ACAQRCMRMBQB
output:
Alice
result:
ok single line: 'Alice'
Test #36:
score: 0
Accepted
time: 27ms
memory: 3508kb
input:
RABQCQMCABMR
output:
Bob
result:
ok single line: 'Bob'
Test #37:
score: 0
Accepted
time: 10ms
memory: 3796kb
input:
QQBARCRBMMAC
output:
Alice
result:
ok single line: 'Alice'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
RQMRQABCABCM
output:
Alice
result:
ok single line: 'Alice'
Test #39:
score: 0
Accepted
time: 5ms
memory: 3580kb
input:
RQAMBRQCCBMA
output:
Alice
result:
ok single line: 'Alice'
Test #40:
score: 0
Accepted
time: 3ms
memory: 3764kb
input:
QQBACMARMRBC
output:
Alice
result:
ok single line: 'Alice'
Test #41:
score: 0
Accepted
time: 12ms
memory: 3512kb
input:
QAQCRRAMMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #42:
score: 0
Accepted
time: 6ms
memory: 3580kb
input:
QQBMCBRARMAC
output:
Bob
result:
ok single line: 'Bob'
Test #43:
score: 0
Accepted
time: 216ms
memory: 3804kb
input:
BABARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #44:
score: 0
Accepted
time: 968ms
memory: 3512kb
input:
BBARARCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #45:
score: 0
Accepted
time: 84ms
memory: 3592kb
input:
BBAARCRCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #46:
score: 0
Accepted
time: 265ms
memory: 3596kb
input:
BBAARRCQCQMM
output:
Bob
result:
ok single line: 'Bob'
Test #47:
score: 0
Accepted
time: 168ms
memory: 3580kb
input:
BBAARRCCQMQM
output:
Bob
result:
ok single line: 'Bob'
Test #48:
score: 0
Accepted
time: 577ms
memory: 3544kb
input:
BBAACCRQMQRM
output:
Bob
result:
ok single line: 'Bob'
Test #49:
score: 0
Accepted
time: 558ms
memory: 3544kb
input:
BACBACQRRQMM
output:
Bob
result:
ok single line: 'Bob'
Test #50:
score: 0
Accepted
time: 1706ms
memory: 3564kb
input:
RAABBRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #51:
score: 0
Accepted
time: 117ms
memory: 3796kb
input:
RABRBQMCACQM
output:
Bob
result:
ok single line: 'Bob'
Test #52:
score: 0
Accepted
time: 1ms
memory: 3468kb
input:
CMMQQABCRABR
output:
Alice
result:
ok single line: 'Alice'
Test #53:
score: 0
Accepted
time: 315ms
memory: 3768kb
input:
RBAABRCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Extra Test:
score: 0
Extra Test Passed