QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#708919 | #7179. Fischer's Chess Guessing Game | thieunguyenhuy | WA | 49ms | 3908kb | C++14 | 4.6kb | 2024-11-04 09:32:58 | 2024-11-04 09:33:08 |
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) ++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);
}
cerr << "Bests " << bests.size() << '\n';
return bests[0];
// 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 3908kb
input:
GAME 1 2 3 1 1 2 8 END
output:
RBBNNQKR RKNBQNBR NRQBNKBR RNKNQRBB BBRKQNNR RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 6 (1 test case)
Test #2:
score: 0
Accepted
time: 44ms
memory: 3864kb
input:
GAME 1 2 3 1 1 2 8 GAME 2 1 4 0 6 8 GAME 3 1 3 6 8 GAME 4 1 3 3 0 8 GAME 5 3 3 3 8 GAME 6 2 5 3 4 8 GAME 7 1 3 4 4 5 8 GAME 8 2 2 3 1 8 GAME 9 2 2 2 1 1 8 GAME 10 1 2 0 8 GAME 11 3 3 4 2 8 GAME 12 2 3 0 3 6 8 GAME 13 2 3 2 3 3 8 GAME 14 2 4 3 3 8 GAME 15 3 4 3 2 8 GAME 16 2 4 6 8 GAME 17 2 5 6 8 GAM...
output:
RBBNNQKR RKNBQNBR NRQBNKBR RNKNQRBB BBRKQNNR RKRBBQNN RBBNNQKR RNQBBKRN BNQNRKRB RKNBBRQN RKRBBNQN RBBNNQKR RNQBBKRN RKNBBRNQ RKRBBNNQ RBBNNQKR RNQBBKRN RKNBBRNQ NBNRBKRQ RKRBQNBN RBBNNQKR RKBNQBRN RKBQNRNB RKRBNQBN RBBNNQKR RKNBQNBR RKNNQRBB RKBBQNRN RKRBNNBQ RBBNNQKR RNQBBKRN RKNBBRNQ RNKRBBNQ RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 48ms
memory: 3844kb
input:
GAME 1 2 5 2 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 2 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 8 GAME 12 3 5 4 3 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 4 1 8 GAME 17 4 1 2 8 GAME 18 3 1 1 0 8...
output:
RBBNNQKR RKNBQNBR RKNNQRBB RKQBBNNR RBBNNQKR RKBNQBRN QRNNBBKR RQNKNBBR RKNBBQNR RBBNNQKR RKNBQNBR RNKBQNBR RKNBBNQR RBBNNQKR RKBNQBRN QRNNBBKR RNKNRQBB RKQBNNBR RBBNNQKR RKNBQNBR RBBNNQKR BBRNQNKR RQBBNKNR RBBQNKRN 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: 49ms
memory: 3848kb
input:
GAME 1 0 2 2 0 3 8 GAME 2 0 1 3 2 8 GAME 3 0 1 4 4 8 GAME 4 0 4 2 1 8 GAME 5 1 1 1 2 3 8 GAME 6 0 3 4 8 GAME 7 1 1 0 3 8 GAME 8 0 0 6 4 8 GAME 9 1 0 2 2 2 8 GAME 10 1 0 4 4 4 8 GAME 11 0 2 2 0 8 GAME 12 2 1 2 6 8 GAME 13 1 2 4 2 8 GAME 14 0 1 5 8 GAME 15 0 1 6 8 GAME 16 0 0 6 8 GAME 17 1 1 3 1 2 8 G...
output:
RBBNNQKR QNRKBNRB BNQRKRNB BNNBRKRQ NRKRQNBB QRKRBBNN RBBNNQKR QNRKBNRB NRKBRNBQ NQRBKRBN NRKRBBQN RBBNNQKR QNRKBNRB NRKBRNBQ NRKBBRQN NRKRBBNQ RBBNNQKR QNRKBNRB BNRKQRNB NNRBBKRQ QRKRBNNB RBBNNQKR RNQBBKRN BNRNKRQB NRBKRBQN NRKBNRBQ NRKRBQNB RBBNNQKR QNRKBNRB NQNRBKRB NRKRBNQB RBBNNQKR RNQBBKRN BNR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: -100
Wrong Answer
time: 8ms
memory: 3680kb
input:
GAME 1 1 2 2 1 1 6
output:
RBBNNQKR RNQBBKRN BRKNQBRN NRBBKRQN BNNRKQRB RKNQRBBN
result:
wrong answer (i) too many guesses in game 1, pos = @