QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#708897#7179. Fischer's Chess Guessing GamethieunguyenhuyWA 65ms3976kbC++144.5kb2024-11-04 09:24:212024-11-04 09:24:21

Judging History

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

  • [2024-11-04 09:24:21]
  • 评测
  • 测评结果:WA
  • 用时:65ms
  • 内存:3976kb
  • [2024-11-04 09:24:21]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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 = @