QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#230571 | #7635. Fairy Chess | ucup-team2303# | AC ✓ | 1012ms | 65632kb | C++17 | 3.3kb | 2023-10-28 19:36:04 | 2023-10-28 19:36:05 |
Judging History
answer
// #pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define PB emplace_back
// #define int long long
#define ll long long
#define vi vector<int>
#define siz(a) ((int) ((a).size()))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
void print(vi n) {rep(i, 0, siz(n) - 1) cerr << n[i] << " \n"[i == siz(n) - 1];}
char s[15];
int p[9][9], dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1}, t[9][9];
#define ull unsigned long long
#define MP make_pair
map<pair<ull, ull>, bool> mp[13];
bool R(int n, int m, int k) {
bool o = 1;
for(int x = n - 1, y = m - 1; x && y; --x, --y) {
p[x][y] += k;
o &= !t[x][y];
}
for(int x = n + 1, y = m - 1; x <= 8 && y; ++x, --y) {
p[x][y] += k;
o &= !t[x][y];
}
for(int x = n - 1, y = m + 1; x && y <= 8; --x, ++y) {
p[x][y] += k;
o &= !t[x][y];
}
for(int x = n + 1, y = m + 1; x <= 8 && y <= 8; ++x, ++y) {
p[x][y] += k;
o &= !t[x][y];
}
return o;
}
bool G(int n, int m, int k) {
bool o = 1;
for(int x = n - 1, y = m; x; --x) {
p[x][y] += k;
o &= !t[x][y];
}
for(int x = n + 1, y = m; x <= 8; ++x) {
p[x][y] += k;
o &= !t[x][y];
}
for(int x = n, y = m - 1; y; --y) {
p[x][y] += k;
o &= !t[x][y];
}
for(int x = n, y = m + 1; y <= 8; ++y) {
p[x][y] += k;
o &= !t[x][y];
}
return o;
}
bool B(int n, int m, int k) {
bool o = 1;
rep(i, 0, 7) {
int x = n + dx[i], y = m + dy[i];
if(x >= 1 && x <= 8 && y >= 1 && y <= 8) {
p[x][y] += k;
o &= !t[x][y];
}
}
return o;
}
bool ins(int n, int m, char o, int k) {
p[n][m] += k;
t[n][m] += k;
bool q = 1;
if(o == 'B') q = R(n, m, k);
else if(o == 'R') q = G(n, m, k);
else if(o == 'Q') q = R(n, m, k) & G(n, m, k);
else if(o == 'A') q = R(n, m, k) & B(n, m, k);
else if(o == 'C') q = G(n, m, k) & B(n, m, k);
else if(o == 'M') q = R(n, m, k) & G(n, m, k) & B(n, m, k);
if(!q) {
// cout << p[n][m] << ' ' << ' ' << t[n][m] << ' ' << k << endl;
p[n][m] -= k, t[n][m] -= k;
if(o == 'B') R(n, m, -k);
else if(o == 'R') G(n, m, -k);
else if(o == 'Q') R(n, m, -k), G(n, m, -k);
else if(o == 'A') R(n, m, -k), B(n, m, -k);
else if(o == 'C') G(n, m, -k), B(n, m, -k);
else if(o == 'M') R(n, m, -k), G(n, m, -k), B(n, m, -k);
}
return q;
}
bool dfs(int n) {
if(n > 12) return 0;
ull sp = 0;
rep(i, 1, 8) rep(j, 1, 8) sp |= ((ull) (!p[i][j])) << ((i - 1) * 8 + j - 1);
ull sq = 0;
rep(i, 1, 8) rep(j, 1, 8) sq |= ((ull) (t[i][j])) << ((i - 1) * 8 + j - 1);
if(!sp) return 0;
if(mp[n].count(MP(sp, sq))) return mp[n][MP(sp, sq)];
rep(i, 1, 8) rep(j, 1, 8) if(!p[i][j]) {
if(n == 1 && i > j) continue;
if(ins(i, j, s[n], 1)) {
if(!dfs(n + 1)) {
ins(i, j, s[n], -1);
return mp[n][MP(sp, sq)] = 1;
}
ins(i, j, s[n], -1);
}
}
return mp[n][MP(sp, sq)] = 0;
}
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> s + 1;
dfs(1) ? cout << "Alice" : cout << "Bob";
return cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl, 0;
}
详细
Test #1:
score: 100
Accepted
time: 107ms
memory: 11828kb
input:
BBAARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 13ms
memory: 5040kb
input:
BAMBAMQQRCCR
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: 0
Accepted
time: 6ms
memory: 4392kb
input:
QQRAACMRMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #4:
score: 0
Accepted
time: 23ms
memory: 5916kb
input:
MBBARQRMACQC
output:
Alice
result:
ok single line: 'Alice'
Test #5:
score: 0
Accepted
time: 6ms
memory: 4444kb
input:
ACQCMQRBBRMA
output:
Alice
result:
ok single line: 'Alice'
Test #6:
score: 0
Accepted
time: 12ms
memory: 5208kb
input:
MRCMABRQCQAB
output:
Alice
result:
ok single line: 'Alice'
Test #7:
score: 0
Accepted
time: 30ms
memory: 5908kb
input:
BBRCMMQAAQRC
output:
Alice
result:
ok single line: 'Alice'
Test #8:
score: 0
Accepted
time: 20ms
memory: 5604kb
input:
RRMCQMACABQB
output:
Alice
result:
ok single line: 'Alice'
Test #9:
score: 0
Accepted
time: 17ms
memory: 5604kb
input:
QMQBMRBACACR
output:
Alice
result:
ok single line: 'Alice'
Test #10:
score: 0
Accepted
time: 10ms
memory: 4772kb
input:
CMRQAQCBBRAM
output:
Alice
result:
ok single line: 'Alice'
Test #11:
score: 0
Accepted
time: 32ms
memory: 6068kb
input:
CABCRQMMRQAB
output:
Alice
result:
ok single line: 'Alice'
Test #12:
score: 0
Accepted
time: 68ms
memory: 8756kb
input:
ARCBBCMQRAQM
output:
Alice
result:
ok single line: 'Alice'
Test #13:
score: 0
Accepted
time: 3ms
memory: 4252kb
input:
ARCMCARMQBBQ
output:
Alice
result:
ok single line: 'Alice'
Test #14:
score: 0
Accepted
time: 34ms
memory: 6836kb
input:
AQABMCQCMRRB
output:
Bob
result:
ok single line: 'Bob'
Test #15:
score: 0
Accepted
time: 12ms
memory: 5160kb
input:
ACMRABRQMCBQ
output:
Alice
result:
ok single line: 'Alice'
Test #16:
score: 0
Accepted
time: 37ms
memory: 7192kb
input:
CBARMBCQMQAR
output:
Bob
result:
ok single line: 'Bob'
Test #17:
score: 0
Accepted
time: 58ms
memory: 7996kb
input:
RBABRQMCAMQC
output:
Bob
result:
ok single line: 'Bob'
Test #18:
score: 0
Accepted
time: 3ms
memory: 4220kb
input:
MBCQBQARRMCA
output:
Alice
result:
ok single line: 'Alice'
Test #19:
score: 0
Accepted
time: 25ms
memory: 6164kb
input:
AMBQRBCQACMR
output:
Bob
result:
ok single line: 'Bob'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
QRAMQMBBCRAC
output:
Alice
result:
ok single line: 'Alice'
Test #21:
score: 0
Accepted
time: 13ms
memory: 4572kb
input:
ARBCQMMBARQC
output:
Alice
result:
ok single line: 'Alice'
Test #22:
score: 0
Accepted
time: 79ms
memory: 11000kb
input:
CACAMBRQQRBM
output:
Bob
result:
ok single line: 'Bob'
Test #23:
score: 0
Accepted
time: 33ms
memory: 6576kb
input:
CQRRMMBQABCA
output:
Bob
result:
ok single line: 'Bob'
Test #24:
score: 0
Accepted
time: 51ms
memory: 7676kb
input:
ABABCQRMMCRQ
output:
Alice
result:
ok single line: 'Alice'
Test #25:
score: 0
Accepted
time: 16ms
memory: 5448kb
input:
CMBRAAQRQMBC
output:
Bob
result:
ok single line: 'Bob'
Test #26:
score: 0
Accepted
time: 4ms
memory: 4304kb
input:
AQBMRMQRBACC
output:
Alice
result:
ok single line: 'Alice'
Test #27:
score: 0
Accepted
time: 23ms
memory: 5612kb
input:
BRACQQMCAMBR
output:
Bob
result:
ok single line: 'Bob'
Test #28:
score: 0
Accepted
time: 6ms
memory: 4588kb
input:
MCCAQBMQRABR
output:
Bob
result:
ok single line: 'Bob'
Test #29:
score: 0
Accepted
time: 40ms
memory: 7440kb
input:
RBQBCRAACMQM
output:
Bob
result:
ok single line: 'Bob'
Test #30:
score: 0
Accepted
time: 14ms
memory: 5072kb
input:
ACRQARMBBQMC
output:
Bob
result:
ok single line: 'Bob'
Test #31:
score: 0
Accepted
time: 3ms
memory: 4232kb
input:
MRCQBCBQRMAA
output:
Alice
result:
ok single line: 'Alice'
Test #32:
score: 0
Accepted
time: 15ms
memory: 5068kb
input:
ACRQQCMMBBAR
output:
Bob
result:
ok single line: 'Bob'
Test #33:
score: 0
Accepted
time: 3ms
memory: 4780kb
input:
MMACQBRQABRC
output:
Bob
result:
ok single line: 'Bob'
Test #34:
score: 0
Accepted
time: 4ms
memory: 4304kb
input:
QACMQABRMCBR
output:
Alice
result:
ok single line: 'Alice'
Test #35:
score: 0
Accepted
time: 24ms
memory: 5768kb
input:
ACAQRCMRMBQB
output:
Alice
result:
ok single line: 'Alice'
Test #36:
score: 0
Accepted
time: 25ms
memory: 5808kb
input:
RABQCQMCABMR
output:
Bob
result:
ok single line: 'Bob'
Test #37:
score: 0
Accepted
time: 16ms
memory: 5532kb
input:
QQBARCRBMMAC
output:
Alice
result:
ok single line: 'Alice'
Test #38:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
RQMRQABCABCM
output:
Alice
result:
ok single line: 'Alice'
Test #39:
score: 0
Accepted
time: 8ms
memory: 4772kb
input:
RQAMBRQCCBMA
output:
Alice
result:
ok single line: 'Alice'
Test #40:
score: 0
Accepted
time: 2ms
memory: 4316kb
input:
QQBACMARMRBC
output:
Alice
result:
ok single line: 'Alice'
Test #41:
score: 0
Accepted
time: 17ms
memory: 5956kb
input:
QAQCRRAMMCBB
output:
Alice
result:
ok single line: 'Alice'
Test #42:
score: 0
Accepted
time: 10ms
memory: 4956kb
input:
QQBMCBRARMAC
output:
Bob
result:
ok single line: 'Bob'
Test #43:
score: 0
Accepted
time: 129ms
memory: 12728kb
input:
BABARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #44:
score: 0
Accepted
time: 753ms
memory: 47828kb
input:
BBARARCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #45:
score: 0
Accepted
time: 90ms
memory: 10632kb
input:
BBAARCRCQQMM
output:
Alice
result:
ok single line: 'Alice'
Test #46:
score: 0
Accepted
time: 159ms
memory: 14148kb
input:
BBAARRCQCQMM
output:
Bob
result:
ok single line: 'Bob'
Test #47:
score: 0
Accepted
time: 118ms
memory: 12016kb
input:
BBAARRCCQMQM
output:
Bob
result:
ok single line: 'Bob'
Test #48:
score: 0
Accepted
time: 350ms
memory: 26532kb
input:
BBAACCRQMQRM
output:
Bob
result:
ok single line: 'Bob'
Test #49:
score: 0
Accepted
time: 346ms
memory: 27308kb
input:
BACBACQRRQMM
output:
Bob
result:
ok single line: 'Bob'
Test #50:
score: 0
Accepted
time: 1012ms
memory: 65632kb
input:
RAABBRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #51:
score: 0
Accepted
time: 77ms
memory: 9000kb
input:
RABRBQMCACQM
output:
Bob
result:
ok single line: 'Bob'
Test #52:
score: 0
Accepted
time: 1ms
memory: 4012kb
input:
CMMQQABCRABR
output:
Alice
result:
ok single line: 'Alice'
Test #53:
score: 0
Accepted
time: 338ms
memory: 26204kb
input:
RBAABRCCQQMM
output:
Alice
result:
ok single line: 'Alice'
Extra Test:
score: 0
Extra Test Passed