QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#708897 | #7179. Fischer's Chess Guessing Game | thieunguyenhuy | WA | 65ms | 3976kb | C++14 | 4.5kb | 2024-11-04 09:24:21 | 2024-11-04 09:24:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define popcount(n) (__builtin_popcountll((n)))
#define clz(n) (__builtin_clzll((n)))
#define ctz(n) (__builtin_ctzll((n)))
#define lg(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))
#define Int __int128
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;
template <class T1, class T2>
bool maximize(T1 &x, T2 y) {
if (x < y) {
x = y;
return true;
}
return false;
}
template <class T1, class T2>
bool minimize(T1 &x, T2 y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <class T>
void remove_duplicate(vector<T> &ve) {
sort (ve.begin(), ve.end());
ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T> T random(T l, T r) {
return uniform_int_distribution<T>(l, r)(rng);
}
template <class T> T random(T r) {
return rng() % r;
}
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
vector<string> states;
bool is960(string position) {
vector<int> where(5, -1);
for (int i = 0; i < 8; ++i) {
if (position[i] == 'R') {
if (where[0] == -1) where[0] = i;
else where[1] = i;
}
if (position[i] == 'B') {
if (where[2] == -1) where[2] = i;
else where[3] = i;
}
if (position[i] == 'K') where[4] = i;
}
if (where[0] > where[4] || where[1] < where[4]) return false;
if (where[2] % 2 == where[3] % 2) return false;
return true;
}
void generate() {
string position = "RRNNBBKQ"; states.clear();
sort (position.begin(), position.end());
do {
if (is960(position)) states.emplace_back(position);
} while (next_permutation(position.begin(), position.end()));
remove_duplicate(states);
cerr << "There are " << states.size() << " positions\n";
}
int count(const string &s, const string &t) {
int ans = 0;
for (int i = 0; i < 8; ++i) if (s[i] == t[i]) {
++ans;
}
return ans;
}
double getEntropy(string candidate, const vector<string> &candidates) {
vector<int> cnt(9, 0); double entropy = 0.0;
for (auto other : candidates) if (other != candidate) ++cnt[count(candidate, other)];
for (int result = 0; result < 9; ++result) {
if (cnt[result] == 0) continue;
double p = 1.0 * cnt[result] / candidates.size();
entropy += p * log2(1.0 / p);
}
return entropy;
}
string findBest(const vector<string> &candidates) {
double bestEntropy = -1.0; vector<string> bests;
for (auto candidate : candidates) {
double entropy = getEntropy(candidate, candidates);
if (maximize(bestEntropy, entropy)) bests.clear();
if (bestEntropy == entropy) bests.emplace_back(candidate);
}
return bests[random(bests.size())];
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
generate();
string firstMove = findBest(states);
// cerr << getEntropy(states[0], states) << '\n';
string input;
while (cin >> input) {
if (input == "END") break;
int testId; cin >> testId;
// string answer; cin >> answer;
vector<string> candidates = states;
for (int _ = 0; _ < 6; ++_) {
string best = (_ == 0 ? firstMove : findBest(candidates));
cout << best << endl;
int correct; cin >> correct;
// int correct = count(best, answer);
if (correct == 8) break;
vector<string> newCandidates;
for (auto other : candidates) if (count(best, other) == correct) {
newCandidates.emplace_back(other);
}
candidates = newCandidates;
cerr << candidates.size() << '\n';
}
// for (auto candidate : candidates) cerr << candidate << '\n';
}
cerr << '\n'; return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 11ms
memory: 3804kb
input:
GAME 1 2 1 3 6 8 END
output:
RKNNQBBR RBBQNNKR RNKRBBQN RKQBBRNN RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 63ms
memory: 3704kb
input:
GAME 1 1 4 3 3 8 GAME 2 2 2 3 3 4 8 GAME 3 2 2 1 2 4 8 GAME 4 2 4 4 4 4 8 GAME 5 2 3 2 8 GAME 6 3 4 3 1 8 GAME 7 2 3 1 1 8 GAME 8 1 3 3 4 8 GAME 9 1 2 1 5 8 GAME 10 3 3 4 4 2 8 GAME 11 1 2 3 2 4 8 GAME 12 2 3 0 3 6 8 GAME 13 3 3 3 2 8 GAME 14 1 2 1 8 GAME 15 2 5 3 8 GAME 16 4 2 1 2 8 GAME 17 2 5 6 8...
output:
RBBQNNKR RNQBBKRN RQNKBBRN BQRBNKRN RKRBBQNN RBBQNNKR RKNNQBBR RBKNBQRN RQNKBNRB RQKBRNBN RKRBBNQN RBBQNNKR RKNNQBBR NRQBNKBR BBRNKQNR RKBBRQNN RKRBBNNQ RBBQNNKR RKNNQBBR RKNBNRBQ RKRNNQBB RKQRNBBN RKRBQNBN RBBQNNKR RKNNQBBR NRQKNBBR RKRBNQBN RBBQNNKR RKBBQNRN RKBNNQRB RNBQKBRN RKRBNNBQ RBBQNNKR RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 63ms
memory: 3976kb
input:
GAME 1 2 5 2 5 8 GAME 2 3 2 3 3 8 GAME 3 2 6 4 8 GAME 4 3 2 1 2 8 GAME 5 2 8 GAME 6 4 1 4 8 GAME 7 3 4 2 2 8 GAME 8 2 4 4 5 8 GAME 9 3 4 2 1 8 GAME 10 4 2 3 6 8 GAME 11 3 3 4 1 8 GAME 12 3 5 4 8 GAME 13 3 2 1 3 8 GAME 14 2 2 5 8 GAME 15 2 2 4 3 8 GAME 16 2 4 2 3 8 GAME 17 4 1 2 8 GAME 18 3 1 1 8 GAM...
output:
RBBNNQKR RKNBQNBR RKNNQRBB RNQBKNBR RKQBBNNR RBBNNQKR RKBNQBRN QRNNBBKR RQNKNBBR RKNBBQNR RBBNNQKR RKNBQNBR RNNBQKBR RKNBBNQR RBBNNQKR RKBNQBRN QRNNBBKR RNKNRQBB RKQBNNBR RBBNNQKR RKNBQNBR RBBNNQKR BBRNQNKR RQBBNKNR RKNBNQBR RBBNNQKR RKBNQBRN RKBQNNRB RBBKQRNN RKQNBBNR RBBNNQKR RKNBQNBR RKNQNRBB RNN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 59ms
memory: 3712kb
input:
GAME 1 0 1 3 3 8 GAME 2 0 0 3 5 8 GAME 3 0 1 1 3 8 GAME 4 1 1 3 2 3 8 GAME 5 0 2 2 4 8 GAME 6 1 1 4 2 2 8 GAME 7 1 1 3 4 3 8 GAME 8 0 0 5 5 8 GAME 9 1 0 3 1 2 8 GAME 10 2 1 1 8 GAME 11 1 0 3 0 8 GAME 12 1 0 4 8 GAME 13 1 1 3 4 3 8 GAME 14 2 0 6 8 GAME 15 2 0 4 3 8 GAME 16 0 3 3 1 8 GAME 17 0 1 2 8 G...
output:
RQBBNNKR BNRQKRNB QBRNBKRN NRKNBQRB QRKRBBNN RQBBNNKR BNRQKRNB QBNRBKRN NRQKBBRN NRKRBBQN RQBBNNKR BNRQKRNB QBRNBKRN NRKNRQBB NRKRBBNQ RQBBNNKR RBQNBKRN BRKNNRQB NRKBQRBN BRNKQNRB QRKRBNNB RQBBNNKR BNRQKRNB NBRKBRQN NRKNQRBB NRKRBQNB RQBBNNKR RBQNBKRN BRKNNRQB BRKNQBNR BRNBKRQN NRKRBNQB RQBBNNKR RBQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 45ms
memory: 3912kb
input:
GAME 1 2 2 3 0 6 8 GAME 2 1 0 3 5 8 GAME 3 2 2 3 0 6 8 GAME 4 2 3 2 8 GAME 5 1 1 2 2 1 8 GAME 6 3 1 0 8 GAME 7 2 1 1 0 3 8 GAME 8 2 2 0 2 8 GAME 9 2 2 0 4 2 8 GAME 10 3 4 2 2 8 GAME 11 4 1 3 8 GAME 12 4 1 4 4 8 GAME 13 2 4 3 1 8 GAME 14 3 2 0 6 8 GAME 15 3 1 2 0 8 GAME 16 1 3 1 5 8 GAME 17 1 3 2 2 8...
output:
RBNNBQKR RKQBNNBR NRNQKBBR BBRQKNNR RNNKRBBQ RQNKRBBN RBNNBQKR BRNQKRNB RKBBRNQN RNBKQBRN RNQKRBBN RBNNBQKR RKQBNNBR NRNQKBBR BBRQKNNR RQNKRBBN RNNKRBBQ RBNNBQKR RKQBNNBR NRNBQKBR RQNKRNBB RBNNBQKR BRNQKRNB NRQBNKBR QBRKNRBN NBBQRKRN RNQKRNBB RBNNBQKR RKQNBBRN BBRNNKQR RNNKRQBB RBNNBQKR RKQBNNBR BQR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 65ms
memory: 3780kb
input:
GAME 1 1 3 2 4 2 8 GAME 2 2 1 2 3 0 8 GAME 3 1 4 2 3 8 GAME 4 2 0 2 4 8 GAME 5 3 1 0 3 8 GAME 6 1 3 1 4 8 GAME 7 0 2 4 3 8 GAME 8 0 2 2 3 8 GAME 9 0 1 2 2 8 GAME 10 1 1 4 1 4 8 GAME 11 1 2 4 2 8 GAME 12 0 1 1 2 8 GAME 13 2 2 1 3 2 8 GAME 14 3 4 2 2 8 GAME 15 1 4 3 4 8 GAME 16 3 4 4 4 8 GAME 17 4 2 0...
output:
RKBBQNNR NRKQNBBR BQRNNBKR BRKBNQRN BRKRNNQB QRBKNBRN RKBBQNNR RQNNBBKR BRKNQRNB NRKBBNRQ RNKBNRBQ NRBKQBRN RKBBQNNR NRKQNBBR BRKQNRNB RNKRNBBQ NRBKNBRQ RKBBQNNR RQNNBBKR BRKBRNQN NRBBNKRQ QRBKNNRB RKBBQNNR QRNBBKNR RKQBNRBN NBBRKNQR NRBKQNRB RKBBQNNR NRKQNBBR BQRNNBKR NRBKRBQN NRBKNQRB RKBBQNNR BBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: -100
Wrong Answer
time: 14ms
memory: 3912kb
input:
GAME 1 2 2 3 2 8 GAME 2 2 2 1 3 2 8 GAME 3 3 3 2 8 GAME 4 3 1 1 3 8 GAME 5 1 1 2 1 3 3
output:
RKQNBBNR RQBBNNKR BBRQNKNR BBNNQRKR RBBQKRNN RKQNBBNR RQBBNNKR BBRQNKNR RBQKRNBN RNBKRQNB RBBNKRQN RKQNBBNR NRBQKBNR BNRNKBQR RBBNKRNQ RKQNBBNR NRBQKBNR RNKRBQNB QBNNBRKR RBQNKRBN RKQNBBNR NRKBNQBR BRNKQRNB BNRNKQRB NBBRKRNQ NBRKBRQN
result:
wrong answer (i) too many guesses in game 5, pos = @