QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #245286 | #7635. Fairy Chess | zhaohaikun | AC ✓ | 1866ms | 3672kb | C++14 | 7.0kb | 2023-11-09 20:21:16 | 2023-11-09 20:21:17 |
Judging History
answer
// Author: kyEEcccccc
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)
constexpr int DX[] = {1, 2, 2, 1, -1, -2, -2, -1}, DY[] = {2, 1, -1, -2, -2, -1, 1, 2};
string s;
int a[8][8], b[8][8];
vector<array<int, 2>> pos;
void add(int x, int y)
{
a[x][y] += 1;
if (a[x][y] == 1) F(i, 0, SZ(pos)) if (pos[i] == array<int, 2>{x, y}) { pos.erase(pos.begin() + i); break; }
}
void dec(int x, int y)
{
a[x][y] -= 1;
if (a[x][y] == 0) pos.push_back({x, y});
}
bool dfs(int cur)
{
auto ss = pos;
for (auto [i, j] : ss)
{
if (s[cur] == 'B')
{
bool ok = true;
F(k, 0, 7)
{
if (i + j - k >= 0 && i + j - k <= 7 && b[k][i + j - k])
{
ok = false;
break;
}
}
F(k, 0, 7)
{
if (j - i + k >= 0 && j - i + k <= 7 && b[k][j - i + k])
{
ok = false;
break;
}
}
if (!ok) continue;
b[i][j] = 1;
F(k, 0, 7)
{
if (i + j - k >= 0 && i + j - k <= 7)
{
add(k, i + j - k);
}
}
F(k, 0, 7)
{
if (j - i + k >= 0 && j - i + k <= 7)
{
add(k, j - i + k);
}
}
bool res = dfs(cur + 1);
b[i][j] = 0;
F(k, 0, 7)
{
if (j - i + k >= 0 && j - i + k <= 7)
{
dec(k, j - i + k);
}
}
F(k, 0, 7)
{
if (i + j - k >= 0 && i + j - k <= 7)
{
dec(k, i + j - k);
}
}
if (!res) return true;
}
else if (s[cur] == 'R')
{
bool ok = true;
F(k, 0, 7)
{
if (b[i][k] || b[k][j])
{
ok = false;
break;
}
}
if (!ok) continue;
F(k, 0, 7)
{
add(i, k);
add(k, j);
}
b[i][j] = 1;
bool res = dfs(cur + 1);
b[i][j] = 0;
F(k, 0, 7)
{
dec(i, k);
dec(k, j);
}
if (!res) return true;
}
else if (s[cur] == 'Q')
{
bool ok = true;
F(k, 0, 7)
{
if (i + j - k >= 0 && i + j - k <= 7 && b[k][i + j - k])
{
ok = false;
break;
}
}
F(k, 0, 7)
{
if (j - i + k >= 0 && j - i + k <= 7 && b[k][j - i + k])
{
ok = false;
break;
}
}
F(k, 0, 7)
{
if (b[i][k] || b[k][j])
{
ok = false;
break;
}
}
if (!ok) continue;
b[i][j] = 1;
F(k, 0, 7)
{
if (i + j - k >= 0 && i + j - k <= 7)
{
add(k, i + j - k);
}
}
F(k, 0, 7)
{
if (j - i + k >= 0 && j - i + k <= 7)
{
add(k, j - i + k);
}
}
F(k, 0, 7)
{
add(i, k);
add(k, j);
}
bool res = dfs(cur + 1);
b[i][j] = 0;
F(k, 0, 7)
{
if (i + j - k >= 0 && i + j - k <= 7)
{
dec(k, i + j - k);
}
}
F(k, 0, 7)
{
if (j - i + k >= 0 && j - i + k <= 7)
{
dec(k, j - i + k);
}
}
F(k, 0, 7)
{
dec(i, k);
dec(k, j);
}
if (!res) return true;
}
else if (s[cur] == 'A')
{
bool ok = true;
F(k, 0, 7)
{
if (i + j - k >= 0 && i + j - k <= 7 && b[k][i + j - k])
{
ok = false;
break;
}
}
F(k, 0, 7)
{
if (j - i + k >= 0 && j - i + k <= 7 && b[k][j - i + k])
{
ok = false;
break;
}
}
F(k, 0, 7)
{
int x = i + DX[k], y = j + DY[k];
if (0 <= x && x <= 7 && 0 <= y && y <= 7 && b[x][y])
{
ok = false;
break;
}
}
if (!ok) continue;
b[i][j] = 1;
F(k, 0, 7)
{
if (i + j - k >= 0 && i + j - k <= 7)
{
add(k, i + j - k);
}
}
F(k, 0, 7)
{
if (j - i + k >= 0 && j - i + k <= 7)
{
add(k, j - i + k);
}
}
F(k, 0, 7)
{
int x = i + DX[k], y = j + DY[k];
if (0 <= x && x <= 7 && 0 <= y && y <= 7)
{
add(x, y);
}
}
bool res = dfs(cur + 1);
b[i][j] = 0;
F(k, 0, 7)
{
if (i + j - k >= 0 && i + j - k <= 7)
{
dec(k, i + j - k);
}
}
F(k, 0, 7)
{
if (j - i + k >= 0 && j - i + k <= 7)
{
dec(k, j - i + k);
}
}
F(k, 0, 7)
{
int x = i + DX[k], y = j + DY[k];
if (0 <= x && x <= 7 && 0 <= y && y <= 7)
{
dec(x, y);
}
}
if (!res) return true;
}
else if (s[cur] == 'C')
{
bool ok = true;
F(k, 0, 7)
{
if (b[i][k] || b[k][j])
{
ok = false;
break;
}
}
F(k, 0, 7)
{
int x = i + DX[k], y = j + DY[k];
if (0 <= x && x <= 7 && 0 <= y && y <= 7 && b[x][y])
{
ok = false;
break;
}
}
if (!ok) continue;
F(k, 0, 7)
{
add(i, k);
add(k, j);
}
F(k, 0, 7)
{
int x = i + DX[k], y = j + DY[k];
if (0 <= x && x <= 7 && 0 <= y && y <= 7)
{
add(x, y);
}
}
b[i][j] = 1;
bool res = dfs(cur + 1);
b[i][j] = 0;
F(k, 0, 7)
{
dec(i, k);
dec(k, j);
}
F(k, 0, 7)
{
int x = i + DX[k], y = j + DY[k];
if (0 <= x && x <= 7 && 0 <= y && y <= 7)
{
dec(x, y);
}
}
if (!res) return true;
}
else
{
bool ok = true;
F(k, 0, 7)
{
if (i + j - k >= 0 && i + j - k <= 7 && b[k][i + j - k])
{
ok = false;
break;
}
}
F(k, 0, 7)
{
if (j - i + k >= 0 && j - i + k <= 7 && b[k][j - i + k])
{
ok = false;
break;
}
}
F(k, 0, 7)
{
if (b[i][k] || b[k][j])
{
ok = false;
break;
}
}
F(k, 0, 7)
{
int x = i + DX[k], y = j + DY[k];
if (0 <= x && x <= 7 && 0 <= y && y <= 7 && b[x][y])
{
ok = false;
break;
}
}
if (!ok) continue;
b[i][j] = 1;
F(k, 0, 7)
{
if (i + j - k >= 0 && i + j - k <= 7)
{
add(k, i + j - k);
}
}
F(k, 0, 7)
{
if (j - i + k >= 0 && j - i + k <= 7)
{
add(k, j - i + k);
}
}
F(k, 0, 7)
{
add(i, k);
add(k, j);
}
F(k, 0, 7)
{
int x = i + DX[k], y = j + DY[k];
if (0 <= x && x <= 7 && 0 <= y && y <= 7)
{
add(x, y);
}
}
bool res = dfs(cur + 1);
b[i][j] = 0;
F(k, 0, 7)
{
if (i + j - k >= 0 && i + j - k <= 7)
{
dec(k, i + j - k);
}
}
F(k, 0, 7)
{
if (j - i + k >= 0 && j - i + k <= 7)
{
dec(k, j - i + k);
}
}
F(k, 0, 7)
{
dec(i, k);
dec(k, j);
}
F(k, 0, 7)
{
int x = i + DX[k], y = j + DY[k];
if (0 <= x && x <= 7 && 0 <= y && y <= 7)
{
dec(x, y);
}
}
if (!res) return true;
}
}
return false;
}
signed main(void)
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(nullptr);
cin >> s;
F(i, 0, 7) F(j, 0, 7) pos.push_back({i, j});
bool res = dfs(0);
if (res) cout << "Alice\n"; else cout << "Bob\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 164ms
memory: 3672kb
input:
BBAARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 14ms
memory: 3544kb
input:
BAMBAMQQRCCR
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: 0
Accepted
time: 6ms
memory: 3600kb
input:
QQRAACMRMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #4:
score: 0
Accepted
time: 18ms
memory: 3600kb
input:
MBBARQRMACQC
output:
Alice
result:
ok single line: 'Alice'
Test #5:
score: 0
Accepted
time: 7ms
memory: 3628kb
input:
ACQCMQRBBRMA
output:
Alice
result:
ok single line: 'Alice'
Test #6:
score: 0
Accepted
time: 8ms
memory: 3596kb
input:
MRCMABRQCQAB
output:
Alice
result:
ok single line: 'Alice'
Test #7:
score: 0
Accepted
time: 31ms
memory: 3544kb
input:
BBRCMMQAAQRC
output:
Alice
result:
ok single line: 'Alice'
Test #8:
score: 0
Accepted
time: 31ms
memory: 3540kb
input:
RRMCQMACABQB
output:
Alice
result:
ok single line: 'Alice'
Test #9:
score: 0
Accepted
time: 13ms
memory: 3652kb
input:
QMQBMRBACACR
output:
Alice
result:
ok single line: 'Alice'
Test #10:
score: 0
Accepted
time: 8ms
memory: 3664kb
input:
CMRQAQCBBRAM
output:
Alice
result:
ok single line: 'Alice'
Test #11:
score: 0
Accepted
time: 37ms
memory: 3540kb
input:
CABCRQMMRQAB
output:
Alice
result:
ok single line: 'Alice'
Test #12:
score: 0
Accepted
time: 81ms
memory: 3548kb
input:
ARCBBCMQRAQM
output:
Alice
result:
ok single line: 'Alice'
Test #13:
score: 0
Accepted
time: 3ms
memory: 3616kb
input:
ARCMCARMQBBQ
output:
Alice
result:
ok single line: 'Alice'
Test #14:
score: 0
Accepted
time: 73ms
memory: 3660kb
input:
AQABMCQCMRRB
output:
Bob
result:
ok single line: 'Bob'
Test #15:
score: 0
Accepted
time: 10ms
memory: 3596kb
input:
ACMRABRQMCBQ
output:
Alice
result:
ok single line: 'Alice'
Test #16:
score: 0
Accepted
time: 56ms
memory: 3512kb
input:
CBARMBCQMQAR
output:
Bob
result:
ok single line: 'Bob'
Test #17:
score: 0
Accepted
time: 94ms
memory: 3576kb
input:
RBABRQMCAMQC
output:
Bob
result:
ok single line: 'Bob'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
MBCQBQARRMCA
output:
Alice
result:
ok single line: 'Alice'
Test #19:
score: 0
Accepted
time: 21ms
memory: 3532kb
input:
AMBQRBCQACMR
output:
Bob
result:
ok single line: 'Bob'
Test #20:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
QRAMQMBBCRAC
output:
Alice
result:
ok single line: 'Alice'
Test #21:
score: 0
Accepted
time: 11ms
memory: 3568kb
input:
ARBCQMMBARQC
output:
Alice
result:
ok single line: 'Alice'
Test #22:
score: 0
Accepted
time: 68ms
memory: 3564kb
input:
CACAMBRQQRBM
output:
Bob
result:
ok single line: 'Bob'
Test #23:
score: 0
Accepted
time: 53ms
memory: 3632kb
input:
CQRRMMBQABCA
output:
Bob
result:
ok single line: 'Bob'
Test #24:
score: 0
Accepted
time: 75ms
memory: 3600kb
input:
ABABCQRMMCRQ
output:
Alice
result:
ok single line: 'Alice'
Test #25:
score: 0
Accepted
time: 22ms
memory: 3600kb
input:
CMBRAAQRQMBC
output:
Bob
result:
ok single line: 'Bob'
Test #26:
score: 0
Accepted
time: 4ms
memory: 3608kb
input:
AQBMRMQRBACC
output:
Alice
result:
ok single line: 'Alice'
Test #27:
score: 0
Accepted
time: 39ms
memory: 3652kb
input:
BRACQQMCAMBR
output:
Bob
result:
ok single line: 'Bob'
Test #28:
score: 0
Accepted
time: 10ms
memory: 3540kb
input:
MCCAQBMQRABR
output:
Bob
result:
ok single line: 'Bob'
Test #29:
score: 0
Accepted
time: 46ms
memory: 3544kb
input:
RBQBCRAACMQM
output:
Bob
result:
ok single line: 'Bob'
Test #30:
score: 0
Accepted
time: 21ms
memory: 3568kb
input:
ACRQARMBBQMC
output:
Bob
result:
ok single line: 'Bob'
Test #31:
score: 0
Accepted
time: 3ms
memory: 3532kb
input:
MRCQBCBQRMAA
output:
Alice
result:
ok single line: 'Alice'
Test #32:
score: 0
Accepted
time: 21ms
memory: 3564kb
input:
ACRQQCMMBBAR
output:
Bob
result:
ok single line: 'Bob'
Test #33:
score: 0
Accepted
time: 9ms
memory: 3572kb
input:
MMACQBRQABRC
output:
Bob
result:
ok single line: 'Bob'
Test #34:
score: 0
Accepted
time: 5ms
memory: 3568kb
input:
QACMQABRMCBR
output:
Alice
result:
ok single line: 'Alice'
Test #35:
score: 0
Accepted
time: 13ms
memory: 3604kb
input:
ACAQRCMRMBQB
output:
Alice
result:
ok single line: 'Alice'
Test #36:
score: 0
Accepted
time: 42ms
memory: 3600kb
input:
RABQCQMCABMR
output:
Bob
result:
ok single line: 'Bob'
Test #37:
score: 0
Accepted
time: 11ms
memory: 3600kb
input:
QQBARCRBMMAC
output:
Alice
result:
ok single line: 'Alice'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
RQMRQABCABCM
output:
Alice
result:
ok single line: 'Alice'
Test #39:
score: 0
Accepted
time: 7ms
memory: 3628kb
input:
RQAMBRQCCBMA
output:
Alice
result:
ok single line: 'Alice'
Test #40:
score: 0
Accepted
time: 6ms
memory: 3616kb
input:
QQBACMARMRBC
output:
Alice
result:
ok single line: 'Alice'
Test #41:
score: 0
Accepted
time: 22ms
memory: 3652kb
input:
QAQCRRAMMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #42:
score: 0
Accepted
time: 16ms
memory: 3648kb
input:
QQBMCBRARMAC
output:
Bob
result:
ok single line: 'Bob'
Test #43:
score: 0
Accepted
time: 224ms
memory: 3592kb
input:
BABARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #44:
score: 0
Accepted
time: 747ms
memory: 3536kb
input:
BBARARCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #45:
score: 0
Accepted
time: 172ms
memory: 3532kb
input:
BBAARCRCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #46:
score: 0
Accepted
time: 223ms
memory: 3632kb
input:
BBAARRCQCQMM
output:
Bob
result:
ok single line: 'Bob'
Test #47:
score: 0
Accepted
time: 166ms
memory: 3548kb
input:
BBAARRCCQMQM
output:
Bob
result:
ok single line: 'Bob'
Test #48:
score: 0
Accepted
time: 861ms
memory: 3572kb
input:
BBAACCRQMQRM
output:
Bob
result:
ok single line: 'Bob'
Test #49:
score: 0
Accepted
time: 818ms
memory: 3580kb
input:
BACBACQRRQMM
output:
Bob
result:
ok single line: 'Bob'
Test #50:
score: 0
Accepted
time: 1866ms
memory: 3600kb
input:
RAABBRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #51:
score: 0
Accepted
time: 165ms
memory: 3564kb
input:
RABRBQMCACQM
output:
Bob
result:
ok single line: 'Bob'
Test #52:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
CMMQQABCRABR
output:
Alice
result:
ok single line: 'Alice'
Test #53:
score: 0
Accepted
time: 296ms
memory: 3664kb
input:
RBAABRCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Extra Test:
score: 0
Extra Test Passed