QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#500402#7179. Fischer's Chess Guessing Gameucup-team1766TL 0ms0kbC++172.2kb2024-08-01 11:15:232024-08-01 11:15:25

Judging History

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

  • [2024-08-01 11:15:25]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-08-01 11:15:23]
  • 提交

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;
}

void solve() {
    vector<string> left(boards.begin(), boards.end());
    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(boards[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]) {
                min_max = i;
            }
        }
        cout << boards[min_max] << endl;

        int match;
        cin >> match;
        if (match == 8) {
            break;
        }

        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) {
        solve();
        cin >> status;
        if (status == "END") {
            break;
        }
        cin >> game;
    }
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

GAME 1
1
0
2
4
0
0

output:

NRBBNKQR
BRNNKBQR
NBRKNQBR
QBRKBRNN
BBNNQRKR
BBNNQRKR
BBNNQRKR

result: