QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#708920 | #7179. Fischer's Chess Guessing Game | thieunguyenhuy | WA | 48ms | 3924kb | C++14 | 4.6kb | 2024-11-04 09:33:36 | 2024-11-04 09:33:38 |
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: 3764kb
input:
GAME 1 3 0 3 8 END
output:
RKNNBBQR BRNQNBKR RKBNQRNB RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 4 (1 test case)
Test #2:
score: 0
Accepted
time: 48ms
memory: 3784kb
input:
GAME 1 1 3 3 8 GAME 2 1 3 3 6 8 GAME 3 1 2 2 4 8 GAME 4 1 2 3 3 8 GAME 5 2 3 3 5 8 GAME 6 2 4 2 1 8 GAME 7 3 2 1 8 GAME 8 2 4 3 4 8 GAME 9 2 3 5 3 8 GAME 10 2 4 6 8 GAME 11 1 3 1 1 8 GAME 12 1 3 1 1 6 8 GAME 13 4 2 1 3 8 GAME 14 2 2 2 3 8 GAME 15 3 4 5 8 GAME 16 3 4 2 6 8 GAME 17 1 2 4 2 8 GAME 18 2...
output:
RNBQNBKR RBQNBKRN BQRBNKRN RKRBBQNN RNBQNBKR RBQNBKRN BQRBNKRN RKRBBQNN RKRBBNQN RNBQNBKR RBQNBKRN QBRNKNBR NQRBBKNR RKRBBNNQ RNBQNBKR RBQNBKRN QBRNKNBR RQKNRNBB RKRBQNBN RNBQNBKR RKNBBNQR RKQNBBRN RKBBRQNN RKRBNQBN RNBQNBKR RKNBBNQR RKNQBRNB QBNRBNKR RKRBNNBQ RNBQNBKR RKBNNQRB RQKBNNBR RKRQBBNN RNB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 44ms
memory: 3900kb
input:
GAME 1 5 4 5 8 GAME 2 4 2 3 3 8 GAME 3 6 4 8 GAME 4 6 4 4 8 GAME 5 5 3 2 3 8 GAME 6 5 3 5 3 8 GAME 7 3 1 2 4 2 8 GAME 8 3 2 3 1 3 8 GAME 9 4 4 1 8 GAME 10 4 5 8 GAME 11 4 4 2 8 GAME 12 3 2 4 5 8 GAME 13 1 3 1 1 1 8 GAME 14 3 0 4 8 GAME 15 2 3 5 2 8 GAME 16 2 2 5 3 8 GAME 17 2 3 4 2 8 GAME 18 3 1 2 4...
output:
RKBBNNQR RKBBNRNQ RQBBKNNR RKQBBNNR RKBBNNQR RKBNNBRQ NRBBNQKR RNQBNKBR RKNBBQNR RKBBNNQR RNBBNKQR RKNBBNQR RKBBNNQR RKBBNRQN RBBKNNQR RKQBNNBR RKBBNNQR RKBBNRNQ NRBBNKQR RKBNRNQB RKNBQNBR RKBBNNQR RKBBRNNQ RQKBNNBR RNKBBNQR RKNBNQBR RKBBNNQR BRNBNQKR RQBNNKRB RKQRNBBN RKNRQNBB RKQNBBNR RKBBNNQR BRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 46ms
memory: 3924kb
input:
GAME 1 1 4 4 8 GAME 2 2 1 2 1 8 GAME 3 1 5 3 8 GAME 4 0 3 1 3 8 GAME 5 0 2 0 8 GAME 6 1 4 4 3 8 GAME 7 2 0 2 2 8 GAME 8 1 3 2 0 8 GAME 9 2 0 3 2 8 GAME 10 1 2 3 4 8 GAME 11 0 1 3 0 8 GAME 12 1 4 6 8 GAME 13 0 3 3 4 8 GAME 14 1 3 3 3 8 GAME 15 0 2 2 1 8 GAME 16 1 3 5 3 8 GAME 17 3 3 0 3 8 GAME 18 2 0...
output:
RKBNNBQR NRKBBQNR BRKRNQNB QRKRBBNN RKBNNBQR RBNQBNKR NRBBQKNR QBBNRKRN NRKRBBQN RKBNNBQR NRKBBQNR BRKBQNNR NRKRBBNQ RKBNNBQR QRNBBKRN NRQBKRBN BRNKQNRB QRKRBNNB RKBNNBQR QRNBBKRN BBRQKNRN NRKRBQNB RKBNNBQR NRKBBQNR BRKRNQNB RBKRBQNN NRKRBNQB RKBNNBQR RBNQBNKR NQBRNKRB BNRKNBRQ QRKRNBBN RKBNNBQR NRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 48ms
memory: 3760kb
input:
GAME 1 3 2 0 8 GAME 2 2 1 4 8 GAME 3 3 2 0 6 8 GAME 4 2 2 3 3 1 8 GAME 5 1 1 1 3 5 8 GAME 6 2 1 6 8 GAME 7 1 0 1 4 8 GAME 8 2 4 3 2 4 8 GAME 9 1 1 1 3 4 8 GAME 10 2 2 3 3 8 GAME 11 4 4 3 1 8 GAME 12 3 1 3 3 2 8 GAME 13 1 2 2 1 8 GAME 14 2 2 4 3 3 8 GAME 15 2 3 1 2 0 8 GAME 16 1 1 3 0 8 GAME 17 1 0 3...
output:
RKNNBBQR BRNQNBKR QBRNBNKR RQNKRBBN RKNNBBQR RBBQNNKR RNNKQRBB RNQKRBBN RKNNBBQR BRNQNBKR QBRNBNKR RQNKRBBN RNNKRBBQ RKNNBBQR RBBQNNKR RBKNRQBN RKRBQNBN NBRNQKBR RQNKRNBB RKNNBBQR NRKBNQBR BQRNNKRB RNBBKNRQ RNBKRQNB RNQKRNBB RKNNBBQR RBBQNNKR RNNKQRBB RNNKRQBB RKNNBBQR NRKBNQBR BNRNQKRB RQBKRNNB RBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 47ms
memory: 3676kb
input:
GAME 1 1 1 5 2 8 GAME 2 2 1 2 5 8 GAME 3 1 2 1 3 1 8 GAME 4 0 3 6 8 GAME 5 1 2 2 2 8 GAME 6 0 3 4 2 8 GAME 7 2 0 2 1 1 8 GAME 8 1 3 1 3 8 GAME 9 2 0 4 5 8 GAME 10 1 2 2 2 5 8 GAME 11 0 2 3 8 GAME 12 1 4 2 2 8 GAME 13 2 2 0 4 1 8 GAME 14 4 1 2 5 8 GAME 15 3 4 5 5 8 GAME 16 2 3 1 0 8 GAME 17 3 4 3 1 8...
output:
RKNNQBBR NRKBBQNR QRBNNKRB QNRNBKRB QRBKNBRN RKNNQBBR RBBQNNKR RNKRBBQN QRBNKBRN NRBKQBRN RKNNQBBR NRKBBQNR BRQNKRNB NBBQNRKR BQRBNNKR NRBKNBRQ RKNNQBBR BQRKNRNB QRBKRNNB QRBKNNRB RKNNQBBR NRKBBQNR BRQNKRNB BRKQNBRN NRBKQNRB RKNNQBBR BQRKNRNB QRBKRNNB QNBRKRNB NRBKNQRB RKNNQBBR RBBQNNKR NNRKRBBQ NQN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: -100
Wrong Answer
time: 33ms
memory: 3776kb
input:
GAME 1 1 0 0 8 GAME 2 3 0 4 8 GAME 3 2 3 2 0 3 8 GAME 4 2 2 5 3 8 GAME 5 2 3 2 0 4 8 GAME 6 3 1 6 8 GAME 7 1 1 1 4 8 GAME 8 2 2 2 8 GAME 9 1 1 0 3 3 8 GAME 10 2 2 2 4 4 8 GAME 11 1 0 2 2 8 GAME 12 3 0 5 4 8 GAME 13 2 1 4 3 8 GAME 14 1 2 1 2 3 8 GAME 15 2 1 5 8 GAME 16 3 1 8 GAME 17 2 1 5 5 8 GAME 18...
output:
RKNNBBQR NRKBNQBR BNRNQKRB RBBQKRNN RKNNBBQR BRNQNBKR RKBNQRNB RBBNKRQN RKNNBBQR RBBQNNKR RKBBQNRN NRQBBNKR RNBKNRQB RBBNKRNQ RKNNBBQR RBBQNNKR RBKNRQBN RQKNRNBB RBQNKRBN RKNNBBQR RBBQNNKR RKBBQNRN NRQBBNKR RBBNKRNQ RBNQKRBN RKNNBBQR BRNQNBKR RQNNKRBB RBNNKRBQ RKNNBBQR NRKBNQBR BQRNNKRB RNBBKNRQ RQB...
result:
wrong answer (i) too many guesses in game 56, pos =