QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#709010#7179. Fischer's Chess Guessing GamethieunguyenhuyAC ✓200ms4040kbC++144.6kb2024-11-04 10:47:312024-11-04 10:47:32

Judging History

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

  • [2024-11-04 10:47:32]
  • 评测
  • 测评结果:AC
  • 用时:200ms
  • 内存:4040kb
  • [2024-11-04 10:47:31]
  • 提交

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

详细

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