QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#414778#7179. Fischer's Chess Guessing GamepandapythonerAC ✓1889ms3916kbC++202.7kb2024-05-19 17:35:492024-05-19 17:35:50

Judging History

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

  • [2024-05-19 17:35:50]
  • 评测
  • 测评结果:AC
  • 用时:1889ms
  • 内存:3916kb
  • [2024-05-19 17:35:49]
  • 提交

answer

#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const ll inf = 1e18;
mt19937 rnd(234);


vector<string> good;


void build() {
    good.clear();
    string s = "KQRRBBNN";
    sort(all(s));
    while (1) {
        int rc = 0;
        bool ok = true;
        int wb = 0;
        for (int i = 0; i < 8; i += 1) {
            if (s[i] == 'R') {
                rc += 1;
            }
            if (s[i] == 'K') {
                if (rc != 1) {
                    ok = false;
                }
            }
            if (s[i] == 'B' and i % 2 == 0) {
                wb += 1;
            }
        }
        if (wb != 1) {
            ok = false;
        }
        if (ok) {
            good.push_back(s);
        }
        if (!next_permutation(all(s))) {
            break;
        }
    }
}


int operator&(const string &a, const string &b){
    int rs = 0;
    for(int i = 0; i < min((int)a.size(), (int)b.size()); i += 1){
        if(a[i] == b[i]){
            rs += 1;
        }
    }
    return rs;
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    build();
    cerr << good.size() << "\n";
    while(1){
        string aboba;
        cin >> aboba;
        if(aboba == "END"){
            break;
        }
        assert(aboba == "GAME");
        int num;
        cin >> num;
        vector<string> rest = good;
        auto make_move = [&](string s){
            cout << s << endl;
            int x;
            cin >> x;
            if(x == 8){
                return true;
            }
            vector<string> nrest;
            for(auto &t: rest){
                if((s & t) == x){
                    nrest.push_back(t);
                }
            }
            rest.swap(nrest);
            return false;
        };
        auto get_goodness = [&](string s) -> flt {
            vector<int> cnt(9);
            for(auto &t: rest){
                cnt[t & s] += 1;
            }
            flt rs = 0;
            for(auto c: cnt){
                rs += c * log(max(c, 1));
            }
            return rs;
        };
        while(1){
            assert(!rest.empty());
            string s = rest[0];
            flt gdns = get_goodness(s);
            for(auto f: good){
                flt fgdns = get_goodness(f);
                if(fgdns < gdns){
                    s = f;
                    gdns = fgdns;
                }
            }
            if(make_move(s)){
                break;
            }
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 22ms
memory: 3836kb

input:

GAME 1
2
3
1
3
2
8
END

output:

RBBNNQKR
RKNBQNBR
NRQBNKBR
RKNNRQBB
RBKQRNBN
RKRBBQNN

result:

ok (c) correct after 1 tests, max moves 6 (1 test case)

Test #2:

score: 0
Accepted
time: 1853ms
memory: 3892kb

input:

GAME 1
2
3
1
3
2
8
GAME 2
1
4
0
6
8
GAME 3
1
3
6
8
GAME 4
1
3
3
5
8
GAME 5
3
3
3
3
8
GAME 6
2
5
5
8
GAME 7
1
3
4
3
8
GAME 8
2
2
5
4
8
GAME 9
2
2
4
2
8
GAME 10
1
2
0
6
8
GAME 11
3
3
4
4
8
GAME 12
2
3
0
2
4
8
GAME 13
2
3
2
4
5
8
GAME 14
2
4
6
8
GAME 15
3
4
1
1
8
GAME 16
2
4
6
4
8
GAME 17
2
5
2
8
GAME ...

output:

RBBNNQKR
RKNBQNBR
NRQBNKBR
RKNNRQBB
RBKQRNBN
RKRBBQNN
RBBNNQKR
RNQBBKRN
BNQNRKRB
RKNBBRQN
RKRBBNQN
RBBNNQKR
RNQBBKRN
RKNBBRNQ
RKRBBNNQ
RBBNNQKR
RNQBBKRN
RKNBBRNQ
RQKBRNBN
RKRBQNBN
RBBNNQKR
RKBNQBRN
RKBQNRNB
BNRBKQNR
RKRBNQBN
RBBNNQKR
RKNBQNBR
RKBBNRNQ
RKRBNNBQ
RBBNNQKR
RNQBBKRN
RKNBBRNQ
QRKNBBNR
RKR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #3:

score: 0
Accepted
time: 1878ms
memory: 3888kb

input:

GAME 1
2
5
4
4
8
GAME 2
3
2
3
2
8
GAME 3
2
6
4
8
GAME 4
3
2
1
3
8
GAME 5
2
8
GAME 6
4
1
6
8
GAME 7
3
4
0
6
8
GAME 8
2
4
4
4
8
GAME 9
3
4
0
8
GAME 10
4
2
3
5
8
GAME 11
3
3
4
1
8
GAME 12
3
5
1
8
GAME 13
3
2
1
4
8
GAME 14
2
2
4
3
8
GAME 15
2
2
3
3
8
GAME 16
2
4
3
2
8
GAME 17
4
1
3
3
8
GAME 18
3
1
1
0
8...

output:

RBBNNQKR
RKNBQNBR
RKBBNRNQ
RKBBQNRN
RKQBBNNR
RBBNNQKR
RKBNQBRN
QRNNBBKR
NBBNRQKR
RKNBBQNR
RBBNNQKR
RKNBQNBR
NBNRBKQR
RKNBBNQR
RBBNNQKR
RKBNQBRN
QRNNBBKR
RBKQRNBN
RKQBNNBR
RBBNNQKR
RKNBQNBR
RBBNNQKR
BBRNQNKR
RQNBNKBR
RKNBNQBR
RBBNNQKR
RKBNQBRN
QRBBNKRN
RKNNBBQR
RKQNBBNR
RBBNNQKR
RKNBQNBR
RKRQNBBN
BBN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #4:

score: 0
Accepted
time: 1881ms
memory: 3748kb

input:

GAME 1
0
2
2
5
8
GAME 2
0
1
3
3
8
GAME 3
0
1
4
4
8
GAME 4
0
4
2
0
8
GAME 5
1
1
2
2
1
8
GAME 6
0
3
4
0
8
GAME 7
1
1
1
1
2
8
GAME 8
0
0
6
4
8
GAME 9
1
0
2
2
2
8
GAME 10
1
0
4
5
8
GAME 11
0
2
2
6
8
GAME 12
2
1
0
2
8
GAME 13
1
2
3
3
8
GAME 14
0
1
5
8
GAME 15
0
1
6
8
GAME 16
0
0
6
8
GAME 17
1
1
0
4
8
GAM...

output:

RBBNNQKR
QNRKBNRB
BNQRKRNB
NRKRQBBN
QRKRBBNN
RBBNNQKR
QNRKBNRB
NRKBRNBQ
BNRKRBQN
NRKRBBQN
RBBNNQKR
QNRKBNRB
NRKBRNBQ
NRKBBRQN
NRKRBBNQ
RBBNNQKR
QNRKBNRB
BNRKQRNB
BNNBRKRQ
QRKRBNNB
RBBNNQKR
RNQBBKRN
NNRQKRBB
BQRKNRNB
BBNRKRQN
NRKRBQNB
RBBNNQKR
QNRKBNRB
NQNRBKRB
BBNQRKRN
NRKRBNQB
RBBNNQKR
RNQBBKRN
NNR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #5:

score: 0
Accepted
time: 1849ms
memory: 3916kb

input:

GAME 1
1
2
2
6
8
GAME 2
1
4
3
1
8
GAME 3
1
2
1
1
3
8
GAME 4
1
1
2
3
2
8
GAME 5
1
3
1
0
8
GAME 6
2
3
1
6
8
GAME 7
3
4
2
8
GAME 8
4
1
2
4
8
GAME 9
4
1
2
3
8
GAME 10
2
1
2
3
8
GAME 11
2
2
3
4
8
GAME 12
2
2
2
1
8
GAME 13
3
2
0
5
8
GAME 14
2
4
3
1
8
GAME 15
3
1
1
0
5
8
GAME 16
3
2
0
3
8
GAME 17
2
2
1
1
2...

output:

RBBNNQKR
RNQBBKRN
BRQNKBRN
RBNKRQBN
RQNKRBBN
RBBNNQKR
RNQBBKRN
BNQNRKRB
BBRQKNRN
RNQKRBBN
RBBNNQKR
RNQBBKRN
BRQNKBRN
QBRKBRNN
BBNNRKRQ
RNNKRBBQ
RBBNNQKR
RNQBBKRN
NNRQKRBB
BQRKNRNB
BRKQNNRB
RQNKRNBB
RBBNNQKR
RNQBBKRN
RKNBBRNQ
QBNRBKRN
RNQKRNBB
RBBNNQKR
RKNBQNBR
NRQBNKBR
RKNNRQBB
RNNKRQBB
RBBNNQKR
RKB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #6:

score: 0
Accepted
time: 1879ms
memory: 3896kb

input:

GAME 1
2
0
3
2
8
GAME 2
1
2
4
1
3
8
GAME 3
2
0
2
1
8
GAME 4
2
1
1
0
4
8
GAME 5
1
1
2
2
0
8
GAME 6
3
2
1
0
8
GAME 7
0
4
1
3
8
GAME 8
0
3
3
2
8
GAME 9
0
3
4
2
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
5
8
GAME 14
1
0
2
8
GAME 15
2
2
1
5
8
GAME 16
3
2
4
2
8
GAME 17
2
2
1
2
2
8...

output:

RBBNNQKR
RKNBQNBR
BBRKNRQN
BQNBRKRN
QRBKNBRN
RBBNNQKR
RNQBBKRN
BRQNKBRN
BBQRKRNN
BRNNQKRB
NRBKQBRN
RBBNNQKR
RKNBQNBR
BBRKNRQN
BNRNQKRB
NRBKNBRQ
RBBNNQKR
RKNBQNBR
RNBQKBNR
BBRNKRQN
NRBBNKRQ
QRBKNNRB
RBBNNQKR
RNQBBKRN
NNRQKRBB
BQRKNRNB
BBNRKRQN
NRBKQNRB
RBBNNQKR
RKBNQBRN
QRNNBBKR
RBKQRNBN
NRBKNQRB
RBB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #7:

score: 0
Accepted
time: 1840ms
memory: 3900kb

input:

GAME 1
3
3
5
5
8
GAME 2
4
2
1
6
8
GAME 3
4
2
1
8
GAME 4
3
3
2
2
5
8
GAME 5
2
3
1
3
5
8
GAME 6
3
2
2
3
1
8
GAME 7
2
2
3
3
2
8
GAME 8
2
2
2
0
8
GAME 9
2
2
1
0
8
GAME 10
3
3
5
3
8
GAME 11
2
1
6
2
8
GAME 12
3
3
4
2
8
GAME 13
1
3
4
0
8
GAME 14
1
5
4
5
8
GAME 15
1
3
5
5
8
GAME 16
2
3
1
5
5
8
GAME 17
2
2
2...

output:

RBBNNQKR
RKBNQBRN
RKBQNRNB
BBQRKRNN
RBBQKRNN
RBBNNQKR
BBRNQNKR
QNBRNBKR
RBBNKRNQ
RBBNKRQN
RBBNNQKR
BBRNQNKR
QNBRNBKR
RBBNKRNQ
RBBNNQKR
RKBNQBRN
RKBQNRNB
NBBQRKRN
RBKNBRQN
RBQNKRBN
RBBNNQKR
RKNBQNBR
NRQBNKBR
RKNNRQBB
RBKQRNBN
RBNQKRBN
RBBNNQKR
RKBNQBRN
QRNNBBKR
NBNRQKBR
NNBBQRKR
RBNNKRBQ
RBBNNQKR
RKN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #8:

score: 0
Accepted
time: 1889ms
memory: 3892kb

input:

GAME 1
1
1
2
0
5
8
GAME 2
1
2
3
4
4
8
GAME 3
2
4
1
1
8
GAME 4
2
3
3
4
8
GAME 5
2
2
2
3
4
8
GAME 6
1
0
1
2
8
GAME 7
1
1
4
1
8
GAME 8
2
0
6
4
8
GAME 9
2
0
4
3
8
GAME 10
0
1
1
8
GAME 11
0
2
4
5
8
GAME 12
0
2
5
3
8
GAME 13
1
0
3
5
8
GAME 14
0
3
1
5
8
GAME 15
1
1
5
6
8
GAME 16
2
1
1
6
8
GAME 17
1
1
6
8
G...

output:

RBBNNQKR
RNQBBKRN
NNRQKRBB
BQRKNRNB
NRKBQNBR
QRNBKNBR
RBBNNQKR
RNQBBKRN
BRQNKBRN
NRBBKRQN
NBQRKRBN
NRQBKNBR
RBBNNQKR
RKNBQNBR
RKRQNBBN
RNKBBRQN
NRNBKQBR
RBBNNQKR
RKNBQNBR
NRQBNKBR
BRNBKQNR
QRNNKBBR
RBBNNQKR
RKNBQNBR
RQKNBBRN
BRNQNBKR
NQRKNBBR
NRQNKBBR
RBBNNQKR
RNQBBKRN
BRKNRNQB
NNRKQRBB
NRNQKBBR
RBB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #9:

score: 0
Accepted
time: 1846ms
memory: 3792kb

input:

GAME 1
3
1
5
2
8
GAME 2
4
2
3
0
8
GAME 3
3
1
3
4
8
GAME 4
2
4
1
0
5
8
GAME 5
2
3
4
5
8
GAME 6
3
0
3
2
8
GAME 7
2
1
6
4
8
GAME 8
2
1
5
6
8
GAME 9
2
1
5
8
GAME 10
1
1
3
2
0
8
GAME 11
1
0
0
5
8
GAME 12
1
2
3
2
0
8
GAME 13
4
1
3
6
8
GAME 14
4
3
6
8
GAME 15
5
1
5
8
GAME 16
3
4
3
1
8
GAME 17
2
2
4
4
8
GAM...

output:

RBBNNQKR
RKBNQBRN
QBBNRKNR
BBNNQRKR
QBBRKNNR
RBBNNQKR
BBRNQNKR
QNBRNBKR
RKQBNRBN
NBBRKQNR
RBBNNQKR
RKBNQBRN
QBBNRKNR
BBRQKNNR
NBBRKNQR
RBBNNQKR
RKNBQNBR
RKRQNBBN
RNKBBRQN
NBNRQKBR
QBNRKNBR
RBBNNQKR
RKNBQNBR
NRQBNKBR
NBNRQKBR
NBQRKNBR
RBBNNQKR
RKBNQBRN
BBQRNKNR
BQNBNRKR
NBNRKQBR
RBBNNQKR
RKNBQNBR
RNB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #10:

score: 0
Accepted
time: 1827ms
memory: 3832kb

input:

GAME 1
3
0
6
3
8
GAME 2
3
2
2
4
8
GAME 3
4
5
3
8
GAME 4
2
2
1
4
8
GAME 5
1
3
2
5
8
GAME 6
2
2
0
3
5
8
GAME 7
3
1
6
5
8
GAME 8
2
1
3
6
8
GAME 9
3
1
4
5
8
GAME 10
4
4
2
3
8
GAME 11
3
0
4
2
8
GAME 12
3
2
2
6
8
GAME 13
1
4
2
4
5
8
GAME 14
1
3
3
2
8
GAME 15
1
4
2
6
8
GAME 16
2
3
5
2
8
GAME 17
2
3
6
8
GAM...

output:

RBBNNQKR
RKBNQBRN
BBQRNKNR
BBNNQRKR
BBRQNKNR
RBBNNQKR
RKBNQBRN
QRNNBBKR
NBNRQKBR
BBRNQKNR
RBBNNQKR
BBRNQNKR
BBQRKNNR
BBRNNKQR
RBBNNQKR
RKNBQNBR
RQKNBBRN
BBRKNNQR
BQRBNKNR
RBBNNQKR
RNQBBKRN
RKNBBRNQ
BBNRQKNR
BNRBQKNR
RBBNNQKR
RKNBQNBR
RQKNBBRN
BBNRKNQR
BNRBKQNR
BNRBNKQR
RBBNNQKR
RKBNQBRN
QBBNRKNR
NBR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #11:

score: 0
Accepted
time: 1724ms
memory: 3900kb

input:

GAME 1
3
1
1
2
4
8
GAME 2
3
1
1
3
8
GAME 3
4
2
3
2
8
GAME 4
4
3
3
3
8
GAME 5
4
3
4
2
8
GAME 6
3
2
5
4
8
GAME 7
3
0
4
5
8
GAME 8
2
5
1
8
GAME 9
4
3
0
8
GAME 10
4
4
1
4
8
GAME 11
3
1
1
4
6
8
GAME 12
3
3
0
2
8
GAME 13
4
3
0
5
8
GAME 14
3
2
3
4
8
GAME 15
5
3
3
8
GAME 16
5
2
4
8
GAME 17
4
2
5
8
GAME 18
4...

output:

RBBNNQKR
RKBNQBRN
QBBNRKNR
BNRNQBKR
RNNBKQBR
RQNBBNKR
RBBNNQKR
RKBNQBRN
QBBNRKNR
BNRNQBKR
RNQBBNKR
RBBNNQKR
BBRNQNKR
QNBRNBKR
RKQBNRBN
RNNBBQKR
RBBNNQKR
BBRNQNKR
RBQNBKRN
BBNNRKQR
RQNNBBKR
RBBNNQKR
BBRNQNKR
RBQNBKRN
RBBNKNRQ
RNQNBBKR
RBBNNQKR
RKBNQBRN
QRNNBBKR
BQNNRBKR
RNNQBBKR
RBBNNQKR
RKBNQBRN
BBQ...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Extra Test:

score: 0
Extra Test Passed