QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#709010 | #7179. Fischer's Chess Guessing Game | thieunguyenhuy | AC ✓ | 200ms | 4040kb | C++14 | 4.6kb | 2024-11-04 10:47:31 | 2024-11-04 10:47:32 |
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) {
if (candidates.size() == 1) return candidates.back();
double bestEntropy = -1.0; vector<string> bests;
for (auto candidate : states) {
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: 5ms
memory: 3924kb
input:
GAME 1 4 3 3 4 8 END
output:
RKBBQNNR RKBQNBRN RBBKNQNR RKQRBNNB RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 185ms
memory: 3684kb
input:
GAME 1 2 3 1 1 2 8 GAME 2 2 4 3 6 8 GAME 3 2 4 3 5 8 GAME 4 1 4 2 1 2 8 GAME 5 1 3 2 0 1 8 GAME 6 1 2 2 2 4 8 GAME 7 3 3 5 1 8 GAME 8 4 1 2 0 8 GAME 9 4 1 3 6 8 GAME 10 2 3 0 2 6 8 GAME 11 3 5 4 1 8 GAME 12 3 6 3 8 GAME 13 2 4 3 3 8 GAME 14 3 3 8 GAME 15 3 3 6 8 GAME 16 1 1 1 2 0 8 GAME 17 2 4 6 2 8...
output:
RQNNBBKR RKQBNNBR NRNBQKBR RNQNKRBB RQNNBKRB RKRBBQNN RQNNBBKR RKQBNNBR RKNRQNBB RKNBBNQR RKRBBNQN RQNNBBKR RKQBNNBR RKNRQNBB RKRNBQNB RKRBBNNQ RQNNBBKR RNBBQKRN BNRNQKRB BNNBRKQR QNRKNBBR RKRBQNBN RQNNBBKR RNBBQKRN RNBKNRQB QNNRBKRB NBBQRKRN RKRBNQBN RQNNBBKR RNBBQKRN QRBBKNNR RBBKNQNR RKRBBQNN RKR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 169ms
memory: 4040kb
input:
GAME 1 6 4 1 8 GAME 2 6 3 2 8 GAME 3 8 GAME 4 5 2 6 8 GAME 5 6 2 2 8 GAME 6 5 2 3 1 8 GAME 7 4 5 3 8 GAME 8 5 6 8 GAME 9 6 1 3 8 GAME 10 3 2 2 6 8 GAME 11 4 4 4 0 8 GAME 12 4 5 1 8 GAME 13 2 3 3 1 4 8 GAME 14 4 2 1 2 8 GAME 15 3 0 2 8 GAME 16 2 2 6 1 8 GAME 17 1 3 2 3 1 8 GAME 18 2 3 3 8 GAME 19 2 1...
output:
RKNBBNQR BNQBRKNR RNNKRQBB RKQBBNNR RKNBBNQR BNQBRKNR NQNRBKRB RKNBBQNR RKNBBNQR RKNBBNQR RKRQBBNN RKQBNRBN RKQBNNBR RKNBBNQR BNQBRKNR QNNRKRBB RKNBQNBR RKNBBNQR RKRQBBNN RBKNBQNR NBRNBKQR RKNBNQBR RKNBBNQR RKNNBBRQ RNQKBNRB RKQNBBNR RKNBBNQR RKRQBBNN RKNQBBNR RKNBBNQR BNQBRKNR RKRBBQNN RKNNBBQR RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 185ms
memory: 3788kb
input:
GAME 1 2 1 0 5 8 GAME 2 1 4 3 2 1 8 GAME 3 2 1 0 6 0 8 GAME 4 3 2 0 3 8 GAME 5 2 0 2 6 8 GAME 6 2 0 4 2 8 GAME 7 0 2 4 4 8 GAME 8 0 3 0 3 8 GAME 9 0 1 0 5 8 GAME 10 1 4 1 3 2 8 GAME 11 1 4 3 1 8 GAME 12 0 1 1 4 8 GAME 13 2 0 6 2 8 GAME 14 2 0 8 GAME 15 3 4 1 3 8 GAME 16 1 4 2 2 4 8 GAME 17 0 2 5 2 8...
output:
RKQBBNNR RQBNNBKR RBNQKNBR BRKRNBNQ QRKRBBNN RKQBBNNR NRKQNBBR NRBNQBKR BNQRNBKR NBNQRKBR NRKRBBQN RKQBBNNR RQBNNBKR RBNQKNBR BRKRNBNQ RKQNNRBB NRKRBBNQ RKQBBNNR BRQBNNKR RKBBNQRN BRKNQBNR QRKRBNNB RKQBBNNR RQBNNBKR BRKBRNQN NRKRBNQB NRKRBQNB RKQBBNNR RQBNNBKR BRKBRNQN BQNRKRNB NRKRBNQB RKQBBNNR BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 200ms
memory: 3840kb
input:
GAME 1 2 2 2 4 2 8 GAME 2 2 2 3 1 2 8 GAME 3 3 2 1 2 8 GAME 4 2 1 5 0 8 GAME 5 2 1 4 0 8 GAME 6 4 0 2 3 8 GAME 7 1 5 2 0 8 GAME 8 1 4 4 2 8 GAME 9 1 3 2 3 1 8 GAME 10 2 1 3 0 8 GAME 11 3 3 3 4 2 8 GAME 12 3 3 4 2 8 GAME 13 1 3 1 4 8 GAME 14 2 1 6 2 8 GAME 15 2 2 3 2 8 GAME 16 1 2 0 5 2 8 GAME 17 2 2...
output:
RNNBBQKR RKBNNBQR RNKNQRBB NQNRKBBR RNKQNRBB RQNKRBBN RNNBBQKR RKBNNBQR RNKNQRBB RKNQBNRB BQNNRBKR RNQKRBBN RNNBBQKR RKNNBQRB NRQNBBKR NBNRKQBR RNNKRBBQ RNNBBQKR RKBNNBQR RBNKQNBR NNRBBKQR RQNKRNBB RNNBBQKR RKBNNBQR RBNKQNBR QBNRBKNR RNQKRNBB RNNBBQKR NRBBQNKR BRKRNQNB NNBQRKRB RNNKRQBB RNNBBQKR RBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 184ms
memory: 3832kb
input:
GAME 1 2 0 3 5 8 GAME 2 1 2 4 1 1 8 GAME 3 2 0 2 1 8 GAME 4 2 1 1 0 1 8 GAME 5 1 1 2 2 2 8 GAME 6 3 2 1 0 3 8 GAME 7 0 4 1 3 8 GAME 8 0 3 3 5 8 GAME 9 0 3 4 3 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 8 GAME 14 1 0 1 0 8 GAME 15 2 2 1 5 1 8 GAME 16 3 2 4 0 8 GAME 17 2 2 1 2...
output:
RBBNNQKR RKNBQNBR BBRKNRQN QRBKNRNB QRBKNBRN RBBNNQKR RNQBBKRN BRQNKBRN BBQRKRNN RKBNRQNB NRBKQBRN RBBNNQKR RKNBQNBR BBRKNRQN BNRNQKRB NRBKNBRQ RBBNNQKR RKNBQNBR RNBQKBNR BBRNKRQN BNQRKRNB QRBKNNRB RBBNNQKR RNQBBKRN NNRQKRBB BQRKNRNB QBBNRNKR NRBKQNRB RBBNNQKR RKBNQBRN QRNNBBKR RNKBRNBQ BRKBNQNR NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 178ms
memory: 3972kb
input:
GAME 1 2 1 4 2 8 GAME 2 2 2 1 6 8 GAME 3 2 2 1 4 2 8 GAME 4 1 1 3 4 1 8 GAME 5 1 0 2 3 8 GAME 6 1 0 1 2 1 8 GAME 7 4 1 4 0 8 GAME 8 3 2 3 2 8 GAME 9 3 2 4 2 8 GAME 10 3 4 2 6 8 GAME 11 2 1 3 4 8 GAME 12 2 2 0 2 4 8 GAME 13 3 1 0 0 8 GAME 14 2 2 2 0 0 8 GAME 15 2 3 1 1 4 8 GAME 16 2 4 4 2 8 GAME 17 1...
output:
RQBBNNKR RKNNQBBR BBRQKNNR NBRKBQNR RBBQKRNN RQBBNNKR RKNNQBBR NBQRNKBR RBBNKRNQ RBBNKRQN RQBBNNKR RKNNQBBR NBQRNKBR RBBNQKRN RQKNBBRN RBBNKRNQ RQBBNNKR BRQKNNRB RKNNBRQB RKQNBBRN RNKBBQNR RBQNKRBN RQBBNNKR BRQKNNRB RNKRBBQN BNRQKBRN RBNQKRBN RQBBNNKR BRQKNNRB RNKRBBQN NNBRKBRQ QNRKNBBR RBNNKRBQ RQB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 188ms
memory: 3840kb
input:
GAME 1 3 1 2 3 2 8 GAME 2 3 1 3 4 8 GAME 3 2 3 3 2 1 8 GAME 4 1 1 2 4 8 GAME 5 1 2 2 3 2 8 GAME 6 1 1 1 3 2 8 GAME 7 0 6 2 4 8 GAME 8 0 4 5 2 8 GAME 9 0 5 6 8 GAME 10 2 0 4 1 4 8 GAME 11 1 1 2 5 1 8 GAME 12 1 1 1 3 0 8 GAME 13 1 2 2 5 1 8 GAME 14 0 8 GAME 15 0 6 3 8 GAME 16 0 3 3 3 8 GAME 17 0 4 4 1...
output:
RQBBNNKR RKBNQNRB BBQNRNKR QNBBRKNR RQNKNRBB QRNBKNBR RQBBNNKR RKBNQNRB BBQNRNKR RNBBKNQR NRQBKNBR RQBBNNKR RKNNQBBR BRQNKBNR BNNQRBKR BRKNQBRN NRNBKQBR RQBBNNKR BRQKNNRB RKNNBRQB BNRNKBQR QRNNKBBR RQBBNNKR BRQKNNRB RNQNBKRB QRBNKRNB NBBRNQKR NRQNKBBR RQBBNNKR BRQKNNRB RKNNBRQB BBNRKQNR BBNRKRQN NRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 175ms
memory: 4036kb
input:
GAME 1 4 3 2 3 8 GAME 2 3 1 5 3 8 GAME 3 4 3 2 2 8 GAME 4 3 1 5 1 8 GAME 5 3 1 6 4 8 GAME 6 2 3 3 2 1 8 GAME 7 2 2 0 5 8 GAME 8 2 2 2 0 8 GAME 9 2 2 3 1 2 8 GAME 10 1 1 1 0 1 8 GAME 11 1 0 4 1 8 GAME 12 1 2 2 0 2 8 GAME 13 5 1 5 8 GAME 14 3 5 6 8 GAME 15 4 2 2 1 8 GAME 16 2 2 2 5 1 8 GAME 17 3 3 1 1...
output:
RBBQNNKR BBRNQNKR RBQKBNRN RKBBNQNR QBBRKNNR RBBQNNKR RKBBQNRN BBQRKNNR BNRQKBNR NBBRKQNR RBBQNNKR BBRNQNKR RBQKBNRN RKBBNQNR NBBRKNQR RBBQNNKR RKBBQNRN BBQRKNNR BQRBNKNR QBNRKNBR RBBQNNKR RKBBQNRN BBQRKNNR NBBRQKNR NBQRKNBR RBBQNNKR RKNNQBBR NRQKNBBR QRBNKBNR BNRNKRQB NBNRKQBR RBBQNNKR RKNNQBBR RQK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 174ms
memory: 3752kb
input:
GAME 1 2 2 6 4 8 GAME 2 1 2 0 4 8 GAME 3 3 3 3 2 2 8 GAME 4 3 4 2 4 8 GAME 5 2 1 2 1 2 8 GAME 6 4 0 4 8 GAME 7 1 3 4 6 8 GAME 8 1 5 0 8 GAME 9 2 4 2 6 8 GAME 10 2 3 1 4 1 8 GAME 11 2 2 6 3 8 GAME 12 1 2 0 6 8 GAME 13 2 2 5 0 8 GAME 14 2 2 6 2 8 GAME 15 3 2 1 3 8 GAME 16 3 3 2 2 8 GAME 17 3 3 3 4 8 G...
output:
RKBBNNQR RBNNBQKR NBRQBKNR BQRKNRNB BBRQNKNR RKBBNNQR NRKQBBNR RNNKBBRQ NBRQNKBR BBRNQKNR RKBBNNQR BRNBNQKR NBBQNRKR NRBBNKRQ NBBRQNKR BBRNNKQR RKBBNNQR BRNBNQKR BRKBRNQN NRQBBKNR BQRBNKNR RKBBNNQR RBNNBQKR RNQKNBBR BRNKNRQB BBQNRNKR BNRBQKNR RKBBNNQR RKBNRQNB BNRNKRQB BNRBNKQR RKBBNNQR NRKQBBNR BQR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 185ms
memory: 3832kb
input:
GAME 1 6 2 3 8 GAME 2 5 2 4 8 GAME 3 5 2 3 8 GAME 4 4 5 2 4 8 GAME 5 3 2 4 5 8 GAME 6 4 4 6 2 8 GAME 7 3 6 3 8 GAME 8 4 1 4 2 8 GAME 9 3 8 GAME 10 1 4 5 2 8 GAME 11 2 3 0 3 3 8 GAME 12 2 3 1 3 8 GAME 13 3 5 5 2 8 GAME 14 3 4 3 2 8 GAME 15 2 5 1 3 8 GAME 16 1 4 6 1 8 GAME 17 1 6 2 1 8 GAME 18 1 4 8 G...
output:
RKNBBNQR BNQBRKNR RKQBRNBN RQNBBNKR RKNBBNQR RKRQBBNN RBQNBKNR RNQBBNKR RKNBBNQR RKRQBBNN RKRBNQBN RNNBBQKR RKNBBNQR RKNNBBRQ RNQKBNRB RBNKBNQR RQNNBBKR RKNBBNQR BRNBNQKR QBRNBNKR RBNNBQKR RNQNBBKR RKNBBNQR RKNNBBRQ RNKQBBNR QRKRBBNN RNNQBBKR RKNBBNQR BRNBNQKR QBBNNRKR BRQBNNKR RKNBBNQR RKNNBBRQ RQB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed