QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#414778 | #7179. Fischer's Chess Guessing Game | pandapythoner | AC ✓ | 1889ms | 3916kb | C++20 | 2.7kb | 2024-05-19 17:35:49 | 2024-05-19 17:35:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const ll inf = 1e18;
mt19937 rnd(234);
vector<string> good;
void build() {
good.clear();
string s = "KQRRBBNN";
sort(all(s));
while (1) {
int rc = 0;
bool ok = true;
int wb = 0;
for (int i = 0; i < 8; i += 1) {
if (s[i] == 'R') {
rc += 1;
}
if (s[i] == 'K') {
if (rc != 1) {
ok = false;
}
}
if (s[i] == 'B' and i % 2 == 0) {
wb += 1;
}
}
if (wb != 1) {
ok = false;
}
if (ok) {
good.push_back(s);
}
if (!next_permutation(all(s))) {
break;
}
}
}
int operator&(const string &a, const string &b){
int rs = 0;
for(int i = 0; i < min((int)a.size(), (int)b.size()); i += 1){
if(a[i] == b[i]){
rs += 1;
}
}
return rs;
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
build();
cerr << good.size() << "\n";
while(1){
string aboba;
cin >> aboba;
if(aboba == "END"){
break;
}
assert(aboba == "GAME");
int num;
cin >> num;
vector<string> rest = good;
auto make_move = [&](string s){
cout << s << endl;
int x;
cin >> x;
if(x == 8){
return true;
}
vector<string> nrest;
for(auto &t: rest){
if((s & t) == x){
nrest.push_back(t);
}
}
rest.swap(nrest);
return false;
};
auto get_goodness = [&](string s) -> flt {
vector<int> cnt(9);
for(auto &t: rest){
cnt[t & s] += 1;
}
flt rs = 0;
for(auto c: cnt){
rs += c * log(max(c, 1));
}
return rs;
};
while(1){
assert(!rest.empty());
string s = rest[0];
flt gdns = get_goodness(s);
for(auto f: good){
flt fgdns = get_goodness(f);
if(fgdns < gdns){
s = f;
gdns = fgdns;
}
}
if(make_move(s)){
break;
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 22ms
memory: 3836kb
input:
GAME 1 2 3 1 3 2 8 END
output:
RBBNNQKR RKNBQNBR NRQBNKBR RKNNRQBB RBKQRNBN RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 6 (1 test case)
Test #2:
score: 0
Accepted
time: 1853ms
memory: 3892kb
input:
GAME 1 2 3 1 3 2 8 GAME 2 1 4 0 6 8 GAME 3 1 3 6 8 GAME 4 1 3 3 5 8 GAME 5 3 3 3 3 8 GAME 6 2 5 5 8 GAME 7 1 3 4 3 8 GAME 8 2 2 5 4 8 GAME 9 2 2 4 2 8 GAME 10 1 2 0 6 8 GAME 11 3 3 4 4 8 GAME 12 2 3 0 2 4 8 GAME 13 2 3 2 4 5 8 GAME 14 2 4 6 8 GAME 15 3 4 1 1 8 GAME 16 2 4 6 4 8 GAME 17 2 5 2 8 GAME ...
output:
RBBNNQKR RKNBQNBR NRQBNKBR RKNNRQBB RBKQRNBN RKRBBQNN RBBNNQKR RNQBBKRN BNQNRKRB RKNBBRQN RKRBBNQN RBBNNQKR RNQBBKRN RKNBBRNQ RKRBBNNQ RBBNNQKR RNQBBKRN RKNBBRNQ RQKBRNBN RKRBQNBN RBBNNQKR RKBNQBRN RKBQNRNB BNRBKQNR RKRBNQBN RBBNNQKR RKNBQNBR RKBBNRNQ RKRBNNBQ RBBNNQKR RNQBBKRN RKNBBRNQ QRKNBBNR RKR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 1878ms
memory: 3888kb
input:
GAME 1 2 5 4 4 8 GAME 2 3 2 3 2 8 GAME 3 2 6 4 8 GAME 4 3 2 1 3 8 GAME 5 2 8 GAME 6 4 1 6 8 GAME 7 3 4 0 6 8 GAME 8 2 4 4 4 8 GAME 9 3 4 0 8 GAME 10 4 2 3 5 8 GAME 11 3 3 4 1 8 GAME 12 3 5 1 8 GAME 13 3 2 1 4 8 GAME 14 2 2 4 3 8 GAME 15 2 2 3 3 8 GAME 16 2 4 3 2 8 GAME 17 4 1 3 3 8 GAME 18 3 1 1 0 8...
output:
RBBNNQKR RKNBQNBR RKBBNRNQ RKBBQNRN RKQBBNNR RBBNNQKR RKBNQBRN QRNNBBKR NBBNRQKR RKNBBQNR RBBNNQKR RKNBQNBR NBNRBKQR RKNBBNQR RBBNNQKR RKBNQBRN QRNNBBKR RBKQRNBN RKQBNNBR RBBNNQKR RKNBQNBR RBBNNQKR BBRNQNKR RQNBNKBR RKNBNQBR RBBNNQKR RKBNQBRN QRBBNKRN RKNNBBQR RKQNBBNR RBBNNQKR RKNBQNBR RKRQNBBN BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 1881ms
memory: 3748kb
input:
GAME 1 0 2 2 5 8 GAME 2 0 1 3 3 8 GAME 3 0 1 4 4 8 GAME 4 0 4 2 0 8 GAME 5 1 1 2 2 1 8 GAME 6 0 3 4 0 8 GAME 7 1 1 1 1 2 8 GAME 8 0 0 6 4 8 GAME 9 1 0 2 2 2 8 GAME 10 1 0 4 5 8 GAME 11 0 2 2 6 8 GAME 12 2 1 0 2 8 GAME 13 1 2 3 3 8 GAME 14 0 1 5 8 GAME 15 0 1 6 8 GAME 16 0 0 6 8 GAME 17 1 1 0 4 8 GAM...
output:
RBBNNQKR QNRKBNRB BNQRKRNB NRKRQBBN QRKRBBNN RBBNNQKR QNRKBNRB NRKBRNBQ BNRKRBQN NRKRBBQN RBBNNQKR QNRKBNRB NRKBRNBQ NRKBBRQN NRKRBBNQ RBBNNQKR QNRKBNRB BNRKQRNB BNNBRKRQ QRKRBNNB RBBNNQKR RNQBBKRN NNRQKRBB BQRKNRNB BBNRKRQN NRKRBQNB RBBNNQKR QNRKBNRB NQNRBKRB BBNQRKRN NRKRBNQB RBBNNQKR RNQBBKRN NNR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 1849ms
memory: 3916kb
input:
GAME 1 1 2 2 6 8 GAME 2 1 4 3 1 8 GAME 3 1 2 1 1 3 8 GAME 4 1 1 2 3 2 8 GAME 5 1 3 1 0 8 GAME 6 2 3 1 6 8 GAME 7 3 4 2 8 GAME 8 4 1 2 4 8 GAME 9 4 1 2 3 8 GAME 10 2 1 2 3 8 GAME 11 2 2 3 4 8 GAME 12 2 2 2 1 8 GAME 13 3 2 0 5 8 GAME 14 2 4 3 1 8 GAME 15 3 1 1 0 5 8 GAME 16 3 2 0 3 8 GAME 17 2 2 1 1 2...
output:
RBBNNQKR RNQBBKRN BRQNKBRN RBNKRQBN RQNKRBBN RBBNNQKR RNQBBKRN BNQNRKRB BBRQKNRN RNQKRBBN RBBNNQKR RNQBBKRN BRQNKBRN QBRKBRNN BBNNRKRQ RNNKRBBQ RBBNNQKR RNQBBKRN NNRQKRBB BQRKNRNB BRKQNNRB RQNKRNBB RBBNNQKR RNQBBKRN RKNBBRNQ QBNRBKRN RNQKRNBB RBBNNQKR RKNBQNBR NRQBNKBR RKNNRQBB RNNKRQBB RBBNNQKR RKB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 1879ms
memory: 3896kb
input:
GAME 1 2 0 3 2 8 GAME 2 1 2 4 1 3 8 GAME 3 2 0 2 1 8 GAME 4 2 1 1 0 4 8 GAME 5 1 1 2 2 0 8 GAME 6 3 2 1 0 8 GAME 7 0 4 1 3 8 GAME 8 0 3 3 2 8 GAME 9 0 3 4 2 8 GAME 10 0 6 0 8 GAME 11 0 5 4 8 GAME 12 1 2 2 3 8 GAME 13 2 1 3 4 5 8 GAME 14 1 0 2 8 GAME 15 2 2 1 5 8 GAME 16 3 2 4 2 8 GAME 17 2 2 1 2 2 8...
output:
RBBNNQKR RKNBQNBR BBRKNRQN BQNBRKRN QRBKNBRN RBBNNQKR RNQBBKRN BRQNKBRN BBQRKRNN BRNNQKRB NRBKQBRN RBBNNQKR RKNBQNBR BBRKNRQN BNRNQKRB NRBKNBRQ RBBNNQKR RKNBQNBR RNBQKBNR BBRNKRQN NRBBNKRQ QRBKNNRB RBBNNQKR RNQBBKRN NNRQKRBB BQRKNRNB BBNRKRQN NRBKQNRB RBBNNQKR RKBNQBRN QRNNBBKR RBKQRNBN NRBKNQRB RBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 1840ms
memory: 3900kb
input:
GAME 1 3 3 5 5 8 GAME 2 4 2 1 6 8 GAME 3 4 2 1 8 GAME 4 3 3 2 2 5 8 GAME 5 2 3 1 3 5 8 GAME 6 3 2 2 3 1 8 GAME 7 2 2 3 3 2 8 GAME 8 2 2 2 0 8 GAME 9 2 2 1 0 8 GAME 10 3 3 5 3 8 GAME 11 2 1 6 2 8 GAME 12 3 3 4 2 8 GAME 13 1 3 4 0 8 GAME 14 1 5 4 5 8 GAME 15 1 3 5 5 8 GAME 16 2 3 1 5 5 8 GAME 17 2 2 2...
output:
RBBNNQKR RKBNQBRN RKBQNRNB BBQRKRNN RBBQKRNN RBBNNQKR BBRNQNKR QNBRNBKR RBBNKRNQ RBBNKRQN RBBNNQKR BBRNQNKR QNBRNBKR RBBNKRNQ RBBNNQKR RKBNQBRN RKBQNRNB NBBQRKRN RBKNBRQN RBQNKRBN RBBNNQKR RKNBQNBR NRQBNKBR RKNNRQBB RBKQRNBN RBNQKRBN RBBNNQKR RKBNQBRN QRNNBBKR NBNRQKBR NNBBQRKR RBNNKRBQ RBBNNQKR RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 1889ms
memory: 3892kb
input:
GAME 1 1 1 2 0 5 8 GAME 2 1 2 3 4 4 8 GAME 3 2 4 1 1 8 GAME 4 2 3 3 4 8 GAME 5 2 2 2 3 4 8 GAME 6 1 0 1 2 8 GAME 7 1 1 4 1 8 GAME 8 2 0 6 4 8 GAME 9 2 0 4 3 8 GAME 10 0 1 1 8 GAME 11 0 2 4 5 8 GAME 12 0 2 5 3 8 GAME 13 1 0 3 5 8 GAME 14 0 3 1 5 8 GAME 15 1 1 5 6 8 GAME 16 2 1 1 6 8 GAME 17 1 1 6 8 G...
output:
RBBNNQKR RNQBBKRN NNRQKRBB BQRKNRNB NRKBQNBR QRNBKNBR RBBNNQKR RNQBBKRN BRQNKBRN NRBBKRQN NBQRKRBN NRQBKNBR RBBNNQKR RKNBQNBR RKRQNBBN RNKBBRQN NRNBKQBR RBBNNQKR RKNBQNBR NRQBNKBR BRNBKQNR QRNNKBBR RBBNNQKR RKNBQNBR RQKNBBRN BRNQNBKR NQRKNBBR NRQNKBBR RBBNNQKR RNQBBKRN BRKNRNQB NNRKQRBB NRNQKBBR RBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 1846ms
memory: 3792kb
input:
GAME 1 3 1 5 2 8 GAME 2 4 2 3 0 8 GAME 3 3 1 3 4 8 GAME 4 2 4 1 0 5 8 GAME 5 2 3 4 5 8 GAME 6 3 0 3 2 8 GAME 7 2 1 6 4 8 GAME 8 2 1 5 6 8 GAME 9 2 1 5 8 GAME 10 1 1 3 2 0 8 GAME 11 1 0 0 5 8 GAME 12 1 2 3 2 0 8 GAME 13 4 1 3 6 8 GAME 14 4 3 6 8 GAME 15 5 1 5 8 GAME 16 3 4 3 1 8 GAME 17 2 2 4 4 8 GAM...
output:
RBBNNQKR RKBNQBRN QBBNRKNR BBNNQRKR QBBRKNNR RBBNNQKR BBRNQNKR QNBRNBKR RKQBNRBN NBBRKQNR RBBNNQKR RKBNQBRN QBBNRKNR BBRQKNNR NBBRKNQR RBBNNQKR RKNBQNBR RKRQNBBN RNKBBRQN NBNRQKBR QBNRKNBR RBBNNQKR RKNBQNBR NRQBNKBR NBNRQKBR NBQRKNBR RBBNNQKR RKBNQBRN BBQRNKNR BQNBNRKR NBNRKQBR RBBNNQKR RKNBQNBR RNB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 1827ms
memory: 3832kb
input:
GAME 1 3 0 6 3 8 GAME 2 3 2 2 4 8 GAME 3 4 5 3 8 GAME 4 2 2 1 4 8 GAME 5 1 3 2 5 8 GAME 6 2 2 0 3 5 8 GAME 7 3 1 6 5 8 GAME 8 2 1 3 6 8 GAME 9 3 1 4 5 8 GAME 10 4 4 2 3 8 GAME 11 3 0 4 2 8 GAME 12 3 2 2 6 8 GAME 13 1 4 2 4 5 8 GAME 14 1 3 3 2 8 GAME 15 1 4 2 6 8 GAME 16 2 3 5 2 8 GAME 17 2 3 6 8 GAM...
output:
RBBNNQKR RKBNQBRN BBQRNKNR BBNNQRKR BBRQNKNR RBBNNQKR RKBNQBRN QRNNBBKR NBNRQKBR BBRNQKNR RBBNNQKR BBRNQNKR BBQRKNNR BBRNNKQR RBBNNQKR RKNBQNBR RQKNBBRN BBRKNNQR BQRBNKNR RBBNNQKR RNQBBKRN RKNBBRNQ BBNRQKNR BNRBQKNR RBBNNQKR RKNBQNBR RQKNBBRN BBNRKNQR BNRBKQNR BNRBNKQR RBBNNQKR RKBNQBRN QBBNRKNR NBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 1724ms
memory: 3900kb
input:
GAME 1 3 1 1 2 4 8 GAME 2 3 1 1 3 8 GAME 3 4 2 3 2 8 GAME 4 4 3 3 3 8 GAME 5 4 3 4 2 8 GAME 6 3 2 5 4 8 GAME 7 3 0 4 5 8 GAME 8 2 5 1 8 GAME 9 4 3 0 8 GAME 10 4 4 1 4 8 GAME 11 3 1 1 4 6 8 GAME 12 3 3 0 2 8 GAME 13 4 3 0 5 8 GAME 14 3 2 3 4 8 GAME 15 5 3 3 8 GAME 16 5 2 4 8 GAME 17 4 2 5 8 GAME 18 4...
output:
RBBNNQKR RKBNQBRN QBBNRKNR BNRNQBKR RNNBKQBR RQNBBNKR RBBNNQKR RKBNQBRN QBBNRKNR BNRNQBKR RNQBBNKR RBBNNQKR BBRNQNKR QNBRNBKR RKQBNRBN RNNBBQKR RBBNNQKR BBRNQNKR RBQNBKRN BBNNRKQR RQNNBBKR RBBNNQKR BBRNQNKR RBQNBKRN RBBNKNRQ RNQNBBKR RBBNNQKR RKBNQBRN QRNNBBKR BQNNRBKR RNNQBBKR RBBNNQKR RKBNQBRN BBQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed