QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#708892#7179. Fischer's Chess Guessing GamethieunguyenhuyWA 47ms3944kbC++144.3kb2024-11-04 09:18:452024-11-04 09:18:46

Judging History

你现在查看的是最新测评结果

  • [2024-11-04 09:18:46]
  • 评测
  • 测评结果:WA
  • 用时:47ms
  • 内存:3944kb
  • [2024-11-04 09:18:45]
  • 提交

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) {
    string best; double bestEntropy = -1.0;
    for (auto candidate : candidates) {
        double entropy = getEntropy(candidate, candidates);
        if (maximize(bestEntropy, entropy)) best = candidate;
    }
    return best;
}

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 << '\n'; return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 3928kb

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: 3784kb

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: 47ms
memory: 3944kb

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: 42ms
memory: 3640kb

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: 3788kb

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 =