QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#500437 | #7179. Fischer's Chess Guessing Game | ucup-team1766 | WA | 14ms | 3968kb | C++17 | 2.5kb | 2024-08-01 11:49:09 | 2024-08-01 11:49:10 |
Judging History
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 = @