QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#230501 | #7635. Fairy Chess | ucup-team2303# | WA | 1ms | 3976kb | C++17 | 2.9kb | 2023-10-28 19:13:50 | 2023-10-28 19:13:51 |
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};
// #define pii pair<int, int>
// #define MP make_pair
// vector<pii> st;
#define ull unsigned long long
map<ull, bool> mp[13];
inline 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 &= p[x][y] <= 1;
}
for(int x = n + 1, y = m - 1; x <= 8 && y; ++x, --y) {
p[x][y] += k;
o &= p[x][y] <= 1;
}
for(int x = n - 1, y = m + 1; x && y <= 8; --x, ++y) {
p[x][y] += k;
o &= p[x][y] <= 1;
}
for(int x = n + 1, y = m + 1; x <= 8 && y <= 8; ++x, ++y) {
p[x][y] += k;
o &= p[x][y] <= 1;
}
return o;
}
inline 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 &= p[x][y] <= 1;
}
for(int x = n + 1, y = m; x <= 8; ++x) {
p[x][y] += k;
o &= p[x][y] <= 1;
}
for(int x = n, y = m - 1; y; --y) {
p[x][y] += k;
o &= p[x][y] <= 1;
}
for(int x = n, y = m + 1; y <= 8; ++y) {
p[x][y] += k;
o &= p[x][y] <= 1;
}
return o;
}
inline 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 &= p[x][y] <= 1;
}
}
return o;
}
inline bool ins(int n, int m, char o, int k) {
p[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) ins(n, m, o, -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);
if(!sp) return 0;
if(mp[n].count(sp)) return mp[n][sp];
// cout << n << ' ' << sp << endl;
rep(i, 1, 8) rep(j, 1, 8) if(!p[i][j]) {
if(ins(i, j, s[n], 1)) {
if(!dfs(n + 1)) {
ins(i, j, s[n], -1);
return mp[n][sp] = 1;
}
ins(i, j, s[n], -1);
}
}
return mp[n][sp] = 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 << "Bob" : cout << "Alice";
return cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl, 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3964kb
input:
BBAARRCCQQMM
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
BAMBAMQQRCCR
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3964kb
input:
QQRAACMRMCBB
output:
Bob
result:
wrong answer 1st lines differ - expected: 'Alice', found: 'Bob'