QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#231926#7635. Fairy Chesstselmegkh#WA 186ms14248kbC++144.1kb2023-10-29 18:09:222023-10-29 18:09:23

Judging History

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

  • [2023-10-29 18:09:23]
  • 评测
  • 测评结果:WA
  • 用时:186ms
  • 内存:14248kb
  • [2023-10-29 18:09:22]
  • 提交

answer

#include <iostream>
#include <vector>
#include <cstring>
#include <array>
#include <map>
#include <unordered_map>
#include <algorithm>
using namespace std;
using ll = long long;
using ull = unsigned long long;
string s;
ull B[64], R[64], K[64], Q[64], A[64], C[64], M[64], T[6][64];
vector<int> t(26);
vector<unordered_map<ull, int>> w(12);
int cnt(ull n) {
    int a = 0;
    while (n) {
        a += n % 2;
        n /= 2;
    }
    return a;
}
int rec(int i, ull a) {
    if (i == s.size()) {
        return 0;
    }
    if (w[i].find(a) != w[i].end()) {
        return w[i][a];
    }
    vector<pair<int, ull>> v;
    for (int x = 0; x < 8; x++) {
        for (int y = 0; y < 8; y++) {
            ull b = T[t[s[i] - 'A']][8 * x + y];
            if ((a >> (8 * x + y) & 1) == 0) {
                v.push_back({cnt((a | b) - a), a | b});
            }
        }
    }
    sort(v.rbegin(), v.rend());
    for (int j = 0; j < v.size() && j < 400; j++) {
        if (!rec(i + 1, v[j].second)) return w[i][a] = 1;
    }
    // for (int j = 0; j < v.size() && j < 150; j++) {
    //     if (!rec(i + 1, v[(int)v.size() - 1 - j].second)) return w[i][a] = 1;
    // }
    return w[i][a] = 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            ull s = 0; int x, y;
            x = i, y = j;
            while (x >= 0 && y >= 0) {
                s += 1ULL << (8 * x + y);
                x--, y--;
            }
            x = i, y = j;
            while (x >= 0 && y < 8) {
                s += 1ULL << (8 * x + y);
                x--, y++;
            }
            x = i, y = j;
            while (x < 8 && y >= 0) {
                s += 1ULL << (8 * x + y);
                x++, y--;
            }
            x = i, y = j;
            while (x < 8 && y < 8) {
                s += 1ULL << (8 * x + y);
                x++, y++;
            }
            B[8 * i + j] = s;
        }
    }
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            ull s = 0; int x, y;
            x = i, y = j;
            while (x >= 0) {
                s += 1ULL << (8 * x + y);
                x--;
            }
            x = i, y = j;
            while (x < 8) {
                s += 1ULL << (8 * x + y);
                x++;
            }
            x = i, y = j;
            while (y >= 0) {
                s += 1ULL << (8 * x + y);
                y--;
            }
            x = i, y = j;
            while (y < 8) {
                s += 1ULL << (8 * x + y);
                y++;
            }
            R[8 * i + j] = s;
        }
    }
    vector<pair<int, int>> p;
    p.emplace_back(0, 0);

    p.emplace_back(-2, -1);
    p.emplace_back(-2, 1);
    p.emplace_back(-1, 2);
    p.emplace_back(1, 2);
    p.emplace_back(2, 1);
    p.emplace_back(2, -1);
    p.emplace_back(1, -2);
    p.emplace_back(-1, -2);
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            ull s = 0; int x, y;
            for (auto [dx, dy] : p) {
                x = i + dx;
                y = j + dy;
                if (x >= 0 && y >= 0 && x < 8 && y < 8) {
                    s += 1ULL << (8 * x + y);
                }
            }
            K[8 * i + j] = s;
        }
    }
    for (int i = 0; i < 64; i++) {
        Q[i] = R[i] | B[i];
        A[i] = B[i] | K[i];
        C[i] = R[i] | K[i];
        M[i] = Q[i] | K[i];
        T[0][i] = B[i];
        T[1][i] = R[i];
        T[2][i] = Q[i];
        T[3][i] = A[i];
        T[4][i] = C[i];
        T[5][i] = M[i];
    }
    t['B' - 'A'] = 0;
    t['R' - 'A'] = 1;
    t['Q' - 'A'] = 2;
    t['A' - 'A'] = 3;
    t['C' - 'A'] = 4;
    t['M' - 'A'] = 5;
    cin >> s;
    for (int i = 0; i < 4; i++) {
        for (int j = i; j < 4; j++) {
            if (!rec(1, T[t[s[0] - 'A']][8 * i + j])) {
                cout << "Alice";
                return 0;
            }
        }
    }
    cout << "Bob";
    // cout << (rec(0, 0) ? "Alice" : "Bob");
}

詳細信息

Test #1:

score: 100
Accepted
time: 75ms
memory: 8800kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

score: 0
Accepted
time: 186ms
memory: 14248kb

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

score: -100
Wrong Answer
time: 61ms
memory: 6524kb

input:

QQRAACMRMCBB

output:

Bob

result:

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