QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#506533#7635. Fairy Chesspandapythoner#WA 1351ms184496kbC++233.6kb2024-08-05 19:00:112024-08-05 19:00:11

Judging History

你现在查看的是最新测评结果

  • [2024-08-05 19:00:11]
  • 评测
  • 测评结果:WA
  • 用时:1351ms
  • 内存:184496kb
  • [2024-08-05 19:00:11]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;


using ll = long long;
using ull = unsigned long long;

#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
#define len(a) ((int)(a).size())


const ll inf = 1e18;
mt19937 rnd(234);


string s;


map<char, vector<ull>> mp;
map<array<ull, 3>, bool> dp;

bool get(ull usd, ull captured, int i) {
    if (i == 12) {
        return false;
    }
    array<ull, 3> arr = { usd, captured, i };
    auto it = dp.find(arr);
    if (it != dp.end()) {
        return it->second;
    }
    bool result = false;
    auto my_capturing = mp[s[i]];
    for (int pos = 0; pos < 64; pos += 1) {
        if ((captured >> pos) % 2 == 1) continue;
        if (my_capturing[pos] & usd != 0) continue;
        ull nusd = usd | (ull(1) << pos);
        ull ncaptured = captured | my_capturing[pos];
        if (!get(nusd, ncaptured, i + 1)) {
            result = true;
            break;
        }
    }
    dp[arr] = result;
    return result;
}



int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    mp.clear();
    for (char c : string("RBQKACM")) {
        vector<ull> capturing(64);
        if (c == 'R') {
            rep(x, 8) rep(y, 8) {
                capturing[x * 8 + y] = 0;
                rep(i, 8) {
                    capturing[x * 8 + y] |= (ull(1) << (x * 8 + i));
                    capturing[x * 8 + y] |= (ull(1) << (i * 8 + y));
                }
            }
        } else if (c == 'B') {
            rep(x, 8) rep(y, 8) {
                capturing[x * 8 + y] = 0;
                rep(i, 8) {
                    int dx = abs(x - i);
                    if (y - dx >= 0)
                        capturing[x * 8 + y] |= (ull(1) << (i * 8 + y - dx));

                    if (y + dx < 8)
                        capturing[x * 8 + y] |= (ull(1) << (i * 8 + y + dx));
                }
            }
        } else if (c == 'Q') {
            rep(x, 8) rep(y, 8) {
                capturing[x * 8 + y] = mp['R'][x * 8 + y] | mp['B'][x * 8 + y];
            }
        } else if (c == 'K') {
            rep(x, 8) rep(y, 8) {
                capturing[x * 8 + y] = (ull(1) << (x * 8 + y));
                for (auto [dx, dy] : { make_pair(1, 2), make_pair(2, 1) }) {
                    for (int sdx = -1; sdx <= 1; sdx += 1) {
                        for (int sdy = -1; sdy <= 1; sdy += 1) {
                            int nx = x + dx * sdx;
                            int ny = y + dy * sdy;
                            if (0 <= nx and nx < 8 and 0 <= ny and ny < 8) {
                                capturing[x * 8 + y] |= (ull(1) << (nx * 8 + ny));
                            }
                        }
                    }
                }
            }
        } else if (c == 'A') {
            rep(x, 8) rep(y, 8) {
                capturing[x * 8 + y] = mp['B'][x * 8 + y] | mp['K'][x * 8 + y];
            }
        } else if (c == 'C') {
            rep(x, 8) rep(y, 8) {
                capturing[x * 8 + y] = mp['R'][x * 8 + y] | mp['K'][x * 8 + y];
            }
        } else if (c == 'M') {
            rep(x, 8) rep(y, 8) {
                capturing[x * 8 + y] = mp['Q'][x * 8 + y] | mp['K'][x * 8 + y];
            }
        }
        mp[c] = capturing;
    }
    cin >> s;
    if (get(0, 0, 0)) {
        cout << "Alice" << "\n";
    } else {
        cout << "Bob" << "\n";
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1351ms
memory: 184496kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

score: 0
Accepted
time: 16ms
memory: 6876kb

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

score: 0
Accepted
time: 7ms
memory: 5120kb

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

score: 0
Accepted
time: 247ms
memory: 43720kb

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

score: 0
Accepted
time: 6ms
memory: 5440kb

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

score: 0
Accepted
time: 10ms
memory: 5768kb

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

score: -100
Wrong Answer
time: 119ms
memory: 25780kb

input:

BBRCMMQAAQRC

output:

Bob

result:

wrong answer 1st lines differ - expected: 'Alice', found: 'Bob'