QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#230252#7635. Fairy Chessucup-team1516#WA 515ms50808kbC++173.8kb2023-10-28 17:57:492023-10-28 17:57:49

Judging History

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

  • [2023-10-28 17:57:49]
  • 评测
  • 测评结果:WA
  • 用时:515ms
  • 内存:50808kb
  • [2023-10-28 17:57:49]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

ull bit(int x) {
    return ((ull)1 << x);
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    auto cid = [&](int x, int y) -> int {
        return x*8+y;
    };

    vector<ull> hi(64),ka(64),ke(64);
    vector<ull> ihi(64),ika(64),ike(64);
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            int id = cid(i,j);

            for (int k = 0; k < 8; ++k) {
                for (int l = 0; l < 8; ++l) {
                    int nid = cid(k,l);
                    if (k == i or j == l) {
                        hi[id] |= bit(nid);
                        ihi[nid] |= bit(id);
                    }
                    if (i+j == k+l or i-j == k-l) {
                        ka[id] |= bit(nid);
                        ika[nid] |= bit(id);
                    }
                    if (abs(k-i) == 1 and abs(j-l) == 2) {
                        ke[id] |= bit(nid);
                        ike[nid] |= bit(id);
                    }
                    if (abs(k-i) == 2 and abs(j-l) == 1) {
                        ke[id] |= bit(nid);
                        ike[nid] |= bit(id);
                    }
                }
            }
        }
    }

    vector<pair<int,int>> init(64);
    for (int i = 0; i < 64; ++i) {
        init[i] = {i/8, i%8};
    }

    string str = "BBAARRCCQQMM";
    cin >> str;
    using V = vector<pair<int,int>>;
    map<pair<V,tuple<ull,ull,ull>>,bool> mp;

    auto slv = [&](auto slv, vector<pair<int,int>> v, ull n1, ull n2, ull n3, int i) -> bool {
        char c = str[i];
        bool hisya = (c == 'R' or c == 'Q' or c == 'C' or c == 'M');
        bool kaku = (c == 'B' or c == 'Q' or c == 'A' or c == 'M');
        bool keima = (c == 'A' or c == 'C' or c == 'M');

        ull okeru = 0;
        V can;
        for (auto &[j,k] : v) {
            okeru |= bit(cid(j,k));
        }
        n1 &= okeru;
        n2 &= okeru;
        n3 &= okeru;

        if (mp.find({v,{n1,n2,n3}}) != mp.end()) {
            return mp[{v,{n1,n2,n3}}];
        }

        for (auto &[j,k] : v) {
            vector<pair<int,int>> nv;
            int id = cid(j,k);

            if (hisya) {
                if (n1&bit(id)) continue;
            }
            if (kaku) {
                if (n2&bit(id)) continue;
            }
            if (keima) {
                if (n3&bit(id)) continue;
            }

            // nvの更新
            ull ng = 0;
            ull nn1 = n1;
            ull nn2 = n2;
            ull nn3 = n3;
            nn1 |= ihi[id];
            nn2 |= ika[id];
            nn3 |= ike[id];
            if (hisya) {
                ng |= hi[id];
            }
            if (kaku) {
                ng |= ka[id];
            }
            if (keima) {
                ng |= ke[id];
            }
            for (auto &[l, m] : v) {
                if (ng&bit(cid(l,m))) continue;
                nv.push_back({l,m});
            }
            auto res = slv(slv, nv, nn1, nn2, nn3, i+1);
            if (!res) {
                mp[{v,{n1,n2,n3}}] = true;
                return true;
            }
        }

        mp[{v,{n1,n2,n3}}] = false;
        return false;
    };

    if (slv(slv, init, 0, 0, 0, 0)) {
        cout << "Alice" << endl;
    }
    else {
        cout << "Bob" << endl;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 515ms
memory: 50808kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

score: 0
Accepted
time: 25ms
memory: 6416kb

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

score: 0
Accepted
time: 9ms
memory: 5208kb

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

score: 0
Accepted
time: 49ms
memory: 8952kb

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

score: 0
Accepted
time: 11ms
memory: 4812kb

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

score: 0
Accepted
time: 21ms
memory: 6372kb

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

score: 0
Accepted
time: 55ms
memory: 10048kb

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

score: 0
Accepted
time: 28ms
memory: 6708kb

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

score: -100
Wrong Answer
time: 92ms
memory: 11884kb

input:

QMQBMRBACACR

output:

Bob

result:

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