QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#500437#7179. Fischer's Chess Guessing Gameucup-team1766WA 14ms3968kbC++172.5kb2024-08-01 11:49:092024-08-01 11:49:10

Judging History

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

  • [2024-08-01 11:49:10]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:3968kb
  • [2024-08-01 11:49:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

vector<string> boards;

bool valid(string &board) {
    vector<int> b_inds;
    vector<int> r_inds;
    int k_ind;
    for (int i = 0; i < board.size(); i++) {
        if (board[i] == 'B') {
            b_inds.push_back(i);
        } else if (board[i] == 'K') {
            k_ind = i;
        } else if (board[i] == 'R') {
            r_inds.push_back(i);
        }
    }
    return ((b_inds[0] % 2) != (b_inds[1] % 2) && k_ind > r_inds[0] && k_ind < r_inds[1]);
}

int match_cnt(string &a, string &b) {
    int ret = 0;
    for (int i = 0; i < a.size(); i++) {
        ret += (a[i] == b[i]);
    }
    return ret;
}

int solve() {
    vector<string> left(boards.begin(), boards.end());
    int cnt = 0;
    while (true) {
        // cnts[i][j] = # of boards left matching j characters with board i
        vector<vector<int>> cnts(boards.size(), vector<int>(9));
        vector<int> max_cnt(boards.size());
        int min_max = 0;
        for (int i = 0; i < boards.size(); i++) {
            for (int j = 0; j < left.size(); j++) {
                cnts[i][match_cnt(left[i], left[j])]++;
            }
            for (int j = 0; j < 9; j++) {
                max_cnt[i] = max(max_cnt[i], cnts[i][j]);
            }
            if (max_cnt[i] < max_cnt[min_max] || max_cnt[i] == max_cnt[min_max] && cnts[i][8] > 0) {
                min_max = i;
            }
        }

        if (left.size() > 2) {
            cout << boards[min_max] << endl;
        } else {
            cout << left[0] << endl;
        }

        int match;
        cin >> match;
        if (match == 8) {
            return 0;
        }
        if (++cnt >= 6) {
            return 1;
        }

        vector<string> next_left;
        for (string board : left) {
            if (match_cnt(boards[min_max], board) == match) {
                next_left.push_back(board);
            }
        }
        left = next_left;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string cur_board = "BBKNNQRR";
    do {
        if (valid(cur_board)) {
            boards.push_back(cur_board);
        }
    } while (next_permutation(cur_board.begin(), cur_board.end()));

    string status;
    int game;
    cin >> status >> game;
    while (true) {
        if (solve()) {
            break;
        }
        cin >> status;
        if (status == "END") {
            break;
        }
        cin >> game;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 3968kb

input:

GAME 1
3
0
4
4
8
END

output:

RQKNBBRN
NRKQNBBR
RKNQBRNB
RBQKBRNN
RKRBBQNN

result:

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

Test #2:

score: -100
Wrong Answer
time: 14ms
memory: 3688kb

input:

GAME 1
3
0
4
4
8
GAME 2
3
0
3
0
3
3

output:

RQKNBBRN
NRKQNBBR
RKNQBRNB
RBQKBRNN
RKRBBQNN
RQKNBBRN
NRKQNBBR
RKNQBRNB
BBQRNKNR
RKBNQNRB
RKBNQNRB

result:

wrong answer (i) too many guesses in game 2, pos = @