QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#708920#7179. Fischer's Chess Guessing GamethieunguyenhuyWA 48ms3924kbC++144.6kb2024-11-04 09:33:362024-11-04 09:33:38

Judging History

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

  • [2024-11-04 09:33:38]
  • 评测
  • 测评结果:WA
  • 用时:48ms
  • 内存:3924kb
  • [2024-11-04 09:33:36]
  • 提交

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 =