QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#164981#7179. Fischer's Chess Guessing Gameucup-team004#AC ✓61ms4304kbC++203.4kb2023-09-05 15:09:502023-09-05 15:09:51

Judging History

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

  • [2023-09-05 15:09:51]
  • 评测
  • 测评结果:AC
  • 用时:61ms
  • 内存:4304kb
  • [2023-09-05 15:09:50]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

int correct(std::string a, std::string b) {
    int ans = 0;
    for (int i = 0; i < 8; i++) {
        ans += (a[i] == b[i]);
    }
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string s = "RQKBBNRN";
    std::sort(s.begin(), s.end());
    
    std::vector<std::string> fig;
    do {
        bool ok = true;
        int r = 0;
        for (auto c : s) {
            if (c == 'R') {
                r++;
            }
            if (c == 'K' && r != 1) {
                ok = false;
            }
        }
        int b[2] {};
        for (int i = 0; i < 8; i++) {
            if (s[i] == 'B') {
                b[i % 2] = 1;
            }
        }
        if (!b[0] || !b[1]) {
            ok = false;
        }
        if (ok) {
            fig.push_back(s);
        }
    } while (std::next_permutation(s.begin(), s.end()));
    
    auto dfs = [&](auto self, const auto &s, int rest) -> std::pair<bool, std::map<std::vector<int>, std::string>> {
        std::map<std::vector<int>, std::string> str;
        if (s.size() <= 1) {
            if (!s.empty()) {
                str[{}] = s[0];
            }
            return {true, str};
        }
        if (rest == 0) {
            return {false, {}};
        }
        // std::cerr << s.size() << " " << rest << "\n";
        std::vector<int> cost(960);
        for (int i = 0; i < 960; i++) {
            int freq[9] {};
            for (auto &x : s) {
                freq[correct(x, fig[i])]++;
            }
            for (int j = 0; j <= 8; j++) {
                cost[i] += freq[j] * freq[j];
            }
        }
        std::vector<int> p(960);
        std::iota(p.begin(), p.end(), 0);
        std::sort(p.begin(), p.end(),
            [&](int i, int j) {
                return cost[i] < cost[j];
            });
        for (auto i : p) {
            std::vector<std::string> ns[9];
            for (auto &x : s) {
                ns[correct(x, fig[i])].push_back(x);
            }
            str.clear();
            str[{}] = {fig[i]};
            bool ok = true;
            for (int j = 0; j <= 8; j++) {
                auto [ok1, str1] = self(self, ns[j], rest - 1);
                if (!ok1) {
                    ok = false;
                    break;
                }
                for (auto [x, y] : str1) {
                    auto v = x;
                    v.insert(v.begin(), j);
                    str[v] = y;
                }
            }
            if (ok) {
                return {true, str};
            }
        }
        return {false, {}};
    };
    
    auto [ok, str] = dfs(dfs, fig, 5);
    // for (auto [x, y] : str) {
    //     std::cerr << "[";
    //     for (auto v : x) {
    //         std::cerr << v << ", ";
    //     }
    //     std::cerr << "] : " << y << "\n";
    // }
    
    while (true) {
        std::string o;
        std::cin >> o;
        
        if (o == "END") {
            break;
        }
        int num;
        std::cin >> num;
        
        std::vector<int> v;
        while (true) {
            auto s = str[v];
            std::cout << s << std::endl;
            int res;
            std::cin >> res;
            if (res == 8) {
                break;
            }
            v.push_back(res);
        }
    }
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 51ms
memory: 4100kb

input:

GAME 1
5
2
8
END

output:

RKQBBNRN
RKNQNRBB
RKRBBQNN

result:

ok (c) correct after 1 tests, max moves 3 (1 test case)

Test #2:

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

input:

GAME 1
5
2
8
GAME 2
6
4
4
8
GAME 3
5
2
6
8
GAME 4
5
3
1
8
GAME 5
4
4
3
5
8
GAME 6
4
3
4
3
8
GAME 7
4
2
4
4
8
GAME 8
4
3
6
2
8
GAME 9
3
5
3
3
8
GAME 10
4
3
5
4
8
GAME 11
3
4
3
2
8
GAME 12
4
4
8
GAME 13
3
4
1
2
8
GAME 14
3
3
4
1
8
GAME 15
2
3
1
4
0
8
GAME 16
3
3
3
4
8
GAME 17
3
2
3
1
4
8
GAME 18
2
4
2...

output:

RKQBBNRN
RKNQNRBB
RKRBBQNN
RKQBBNRN
RKBNRNQB
QNRBBKRN
RKRBBNQN
RKQBBNRN
RKNQNRBB
RKRBBQNN
RKRBBNNQ
RKQBBNRN
RKNQNRBB
BRNBNKRQ
RKRBQNBN
RKQBBNRN
RKNNRQBB
RKRNBNQB
RKNBBQRN
RKRBNQBN
RKQBBNRN
RKNNRQBB
RKRNBBNQ
RNKBBRNQ
RKRBNNBQ
RKQBBNRN
RKNNRQBB
RQNKBBRN
RNBQKBRN
RKRQBBNN
RKQBBNRN
RKNNRQBB
RKRNBBNQ
NRK...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #3:

score: 0
Accepted
time: 57ms
memory: 4304kb

input:

GAME 1
6
3
3
8
GAME 2
4
4
3
6
8
GAME 3
5
3
2
8
GAME 4
5
4
5
8
GAME 5
4
4
3
4
8
GAME 6
3
4
5
3
8
GAME 7
4
3
6
1
8
GAME 8
3
8
GAME 9
3
6
1
8
GAME 10
3
4
2
3
8
GAME 11
2
4
1
4
8
GAME 12
2
3
1
4
1
8
GAME 13
3
3
3
1
8
GAME 14
4
1
5
2
8
GAME 15
3
3
2
8
GAME 16
3
1
3
2
8
GAME 17
2
5
0
8
GAME 18
2
4
4
5
8
G...

output:

RKQBBNRN
RKBNRNQB
RKBRQBNN
RKQBBNNR
RKQBBNRN
RKNNRQBB
RKRNBNQB
RKNBBQRN
RKNBBQNR
RKQBBNRN
RKNQNRBB
BRNBNKRQ
RKNBBNQR
RKQBBNRN
RKNQNRBB
RKQRNBBN
RKQBNNBR
RKQBBNRN
RKNNRQBB
RKRNBNQB
RKNBBQRN
RKNBQNBR
RKQBBNRN
RKNQBBNR
RNNBBQKR
RBBKNNQR
RKNBNQBR
RKQBBNRN
RKNNRQBB
RKRNBBNQ
NRKRBNQB
RKQNBBNR
RKQBBNRN
RKN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #4:

score: 0
Accepted
time: 52ms
memory: 4068kb

input:

GAME 1
2
1
4
3
8
GAME 2
2
1
2
3
1
8
GAME 3
1
0
3
1
8
GAME 4
2
1
3
4
2
8
GAME 5
1
1
2
1
2
8
GAME 6
2
1
1
0
8
GAME 7
1
1
1
1
5
8
GAME 8
1
0
4
3
0
8
GAME 9
0
0
4
6
8
GAME 10
1
1
2
0
8
GAME 11
1
0
6
3
8
GAME 12
0
1
2
0
8
GAME 13
2
3
1
1
2
8
GAME 14
3
0
3
0
8
GAME 15
2
2
4
1
3
8
GAME 16
1
0
4
4
2
8
GAME ...

output:

RKQBBNRN
RNKBNQBR
QBBRKRNN
BRKBNRQN
QRKRBBNN
RKQBBNRN
RNKBNQBR
QBBRKRNN
QNBRKBRN
RBBNKNQR
NRKRBBQN
RKQBBNRN
RNBBNQKR
NRKQRNBB
NBRKRQBN
NRKRBBNQ
RKQBBNRN
RNKBNQBR
QBBRKRNN
QBNRBNKR
QRNBKRBN
QRKRBNNB
RKQBBNRN
RNBBNQKR
QBRKBNNR
BBQNRKNR
QRNKRNBB
NRKRBQNB
RKQBBNRN
RNKBNQBR
QBBRKRNN
BNRKQBRN
NRKRBNQB
RKQ...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #5:

score: 0
Accepted
time: 57ms
memory: 4100kb

input:

GAME 1
2
2
1
6
2
8
GAME 2
3
2
4
0
8
GAME 3
1
2
3
4
2
8
GAME 4
2
2
2
4
4
8
GAME 5
3
1
2
1
3
8
GAME 6
1
3
2
1
8
GAME 7
2
1
5
6
8
GAME 8
2
2
1
2
5
8
GAME 9
1
3
0
8
GAME 10
4
1
4
2
8
GAME 11
3
3
3
2
8
GAME 12
2
1
3
3
0
8
GAME 13
3
1
6
2
8
GAME 14
2
2
1
4
2
8
GAME 15
1
2
1
3
3
8
GAME 16
1
3
0
6
8
GAME 17...

output:

RKQBBNRN
RNKBNQBR
BRNBKNQR
RNNKRBBQ
QRNNBBKR
RQNKRBBN
RKQBBNRN
RKNQBBNR
RNQBKNBR
QRBBNNKR
RNQKRBBN
RKQBBNRN
RNBBNQKR
NNBRKBRQ
RBBKRNNQ
RBBKQRNN
RNNKRBBQ
RKQBBNRN
RNKBNQBR
BRNBKNQR
RBNQKNBR
QBRKRNBN
RQNKRNBB
RKQBBNRN
RKNQBBNR
RBBKNRQN
RBNNBKRQ
NRQNKRBB
RNQKRNBB
RKQBBNRN
RNBBNQKR
NRNBQKBR
QNRNBBKR
RNN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #6:

score: 0
Accepted
time: 59ms
memory: 4072kb

input:

GAME 1
2
1
3
1
2
8
GAME 2
2
0
3
5
8
GAME 3
1
2
5
2
8
GAME 4
2
1
2
3
2
8
GAME 5
2
0
5
1
8
GAME 6
1
3
2
0
8
GAME 7
3
3
2
1
8
GAME 8
4
0
2
4
8
GAME 9
2
0
2
1
8
GAME 10
3
2
1
4
2
8
GAME 11
4
1
3
0
8
GAME 12
2
1
0
2
3
8
GAME 13
1
2
1
1
3
8
GAME 14
0
2
4
4
4
8
GAME 15
0
1
5
4
8
GAME 16
0
1
3
5
8
GAME 17
0...

output:

RKQBBNRN
RNKBNQBR
QBBRKRNN
QBNRBNKR
QBNRKRBN
QRBKNBRN
RKQBBNRN
RNKBNQBR
NQBRKNRB
NRBKQRNB
NRBKQBRN
RKQBBNRN
RNBBNQKR
NNBRKBRQ
QBBNRKRN
NRBKNBRQ
RKQBBNRN
RNKBNQBR
QBBRKRNN
QNBRKBRN
RBBNKNQR
QRBKNNRB
RKQBBNRN
RNKBNQBR
NQBRKNRB
BQRNKBRN
NRBKQNRB
RKQBBNRN
RNBBNQKR
NRNBQKBR
QNRNBBKR
NRBKNQRB
RKQBBNRN
RKN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #7:

score: 0
Accepted
time: 52ms
memory: 4080kb

input:

GAME 1
2
1
6
1
8
GAME 2
2
1
5
4
8
GAME 3
1
2
3
5
8
GAME 4
3
1
4
4
8
GAME 5
2
2
2
6
8
GAME 6
1
1
1
1
1
8
GAME 7
3
2
3
0
8
GAME 8
3
1
5
2
8
GAME 9
2
3
2
4
3
8
GAME 10
1
2
2
0
4
8
GAME 11
1
3
0
4
8
GAME 12
1
3
0
3
8
GAME 13
3
2
4
1
8
GAME 14
4
2
2
1
8
GAME 15
2
4
1
2
8
GAME 16
1
1
0
2
3
8
GAME 17
2
3
1...

output:

RKQBBNRN
RNKBNQBR
QBBRKRNN
QRNNKBBR
RBBQKRNN
RKQBBNRN
RNKBNQBR
QBBRKRNN
RBBKNRNQ
RBBNKRQN
RKQBBNRN
RNBBNQKR
NNBRKBRQ
RBBKRNNQ
RBBNKRNQ
RKQBBNRN
RKNQBBNR
RBBKNRQN
BRQBKRNN
RBQNKRBN
RKQBBNRN
RNKBNQBR
BRNBKNQR
RBNQKNBR
RBNQKRBN
RKQBBNRN
RNBBNQKR
QBRKBNNR
BQRNNKRB
BRKRNBNQ
RBNNKRBQ
RKQBBNRN
RKNQBBNR
RNQ...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #8:

score: 0
Accepted
time: 57ms
memory: 4012kb

input:

GAME 1
2
3
4
3
8
GAME 2
3
1
0
1
8
GAME 3
1
3
6
2
8
GAME 4
0
1
3
3
4
8
GAME 5
1
1
1
1
2
8
GAME 6
0
2
2
3
8
GAME 7
1
0
1
6
8
GAME 8
1
0
0
2
8
GAME 9
0
5
3
4
8
GAME 10
2
1
4
4
8
GAME 11
2
2
4
5
8
GAME 12
1
2
3
2
0
8
GAME 13
0
6
2
3
8
GAME 14
0
8
GAME 15
0
6
3
8
GAME 16
1
0
1
4
8
GAME 17
1
0
3
5
8
GAME ...

output:

RKQBBNRN
RNKBNQBR
QNRBBNKR
NRNKBBQR
QRNBKNBR
RKQBBNRN
RKNQBBNR
RBBKNRQN
NQNRBKRB
NRQBKNBR
RKQBBNRN
RNBBNQKR
NRNBQKBR
QRNKBBRN
NRNBKQBR
RKQBBNRN
BNRQKRNB
BQNRNBKR
NRBQNBKR
QRNNBKRB
QRNNKBBR
RKQBBNRN
RNBBNQKR
QBRKBNNR
BQRNNKRB
BRKRNBNQ
NRQNKBBR
RKQBBNRN
BNRQKRNB
BNRNQBKR
RBKQNNBR
NRNQKBBR
RKQBBNRN
RNB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #9:

score: 0
Accepted
time: 61ms
memory: 4008kb

input:

GAME 1
1
2
3
4
3
8
GAME 2
0
2
1
2
8
GAME 3
1
2
4
3
0
8
GAME 4
1
1
4
3
3
8
GAME 5
2
2
3
4
5
8
GAME 6
0
1
3
2
8
GAME 7
0
3
3
1
8
GAME 8
0
2
2
1
8
GAME 9
0
2
3
2
1
8
GAME 10
0
2
3
1
8
GAME 11
0
1
5
1
8
GAME 12
1
2
5
0
8
GAME 13
3
2
1
4
4
8
GAME 14
3
1
4
1
8
GAME 15
2
2
0
4
3
8
GAME 16
5
1
2
8
GAME 17
4...

output:

RKQBBNRN
RNBBNQKR
NNBRKBRQ
RBBKRNNQ
RBBKQRNN
QBBRKNNR
RKQBBNRN
BNRQKRNB
BNRNQBKR
NRNBKRBQ
NBBRKQNR
RKQBBNRN
RNBBNQKR
NNBRKBRQ
NBBNRKRQ
QRNKRBBN
NBBRKNQR
RKQBBNRN
RNBBNQKR
QBRKBNNR
NBRQNKBR
QRKRBNNB
QBNRKNBR
RKQBBNRN
RNKBNQBR
BRNBKNQR
NBBQRNKR
QBBRKNNR
NBQRKNBR
RKQBBNRN
BNRQKRNB
BQNRNBKR
NRBQNBKR
NBN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #10:

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

input:

GAME 1
0
4
5
2
8
GAME 2
0
3
3
2
8
GAME 3
0
2
4
1
8
GAME 4
1
3
3
1
3
8
GAME 5
1
3
4
5
8
GAME 6
1
4
6
1
8
GAME 7
1
1
6
3
8
GAME 8
1
1
5
2
0
8
GAME 9
1
1
4
5
8
GAME 10
0
1
2
4
2
8
GAME 11
0
2
2
5
8
GAME 12
0
1
1
2
8
GAME 13
2
3
6
2
8
GAME 14
2
2
2
1
0
8
GAME 15
2
3
5
3
8
GAME 16
1
4
4
4
8
GAME 17
1
3
5...

output:

RKQBBNRN
BNRQKRNB
BQRKNBNR
BNQNRBKR
BBRQNKNR
RKQBBNRN
BNRQKRNB
BNRQNBKR
BQNRNKRB
BBRNQKNR
RKQBBNRN
BNRQKRNB
BNRNQBKR
NRNQBBKR
BBRNNKQR
RKQBBNRN
RNBBNQKR
NRNBQKBR
RQNNKRBB
QNNBRKBR
BQRBNKNR
RKQBBNRN
RNBBNQKR
NRNBQKBR
BNRBKRNQ
BNRBQKNR
RKQBBNRN
RNBBNQKR
BRNBNKQR
QNNRKRBB
BNRBNKQR
RKQBBNRN
RNBBNQKR
QBR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #11:

score: 0
Accepted
time: 54ms
memory: 4304kb

input:

GAME 1
4
2
4
1
8
GAME 2
5
1
4
8
GAME 3
3
4
8
GAME 4
2
2
2
3
1
8
GAME 5
3
4
5
2
8
GAME 6
2
3
4
4
8
GAME 7
3
1
1
3
2
8
GAME 8
2
2
6
2
8
GAME 9
1
5
0
8
GAME 10
1
3
2
4
8
GAME 11
0
2
4
6
8
GAME 12
0
1
5
2
8
GAME 13
2
3
5
2
8
GAME 14
2
2
4
0
8
GAME 15
1
6
5
8
GAME 16
0
0
5
1
8
GAME 17
0
1
4
2
8
GAME 18
0...

output:

RKQBBNRN
RKNNRQBB
RQNKBBRN
RNBQKBRN
RQNBBNKR
RKQBBNRN
RKNQNRBB
RNNKBBQR
RNQBBNKR
RKQBBNRN
RKNQBBNR
RNNBBQKR
RKQBBNRN
RNKBNQBR
BRNBKNQR
RBNQKNBR
QRKNNRBB
RQNNBBKR
RKQBBNRN
RKNQBBNR
RNNBBQKR
RBBKNNQR
RNQNBBKR
RKQBBNRN
RNKBNQBR
QNRBBNKR
NRNKBBQR
RNNQBBKR
RKQBBNRN
RKNQBBNR
RBBKNRQN
BRQNKBRN
RBBKNNRQ
BRQ...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Extra Test:

score: 0
Extra Test Passed