QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#175628#7179. Fischer's Chess Guessing GameKKT89AC ✓728ms3976kbC++173.5kb2023-09-10 20:49:492023-09-10 20:49:49

Judging History

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

  • [2023-09-10 20:49:49]
  • 评测
  • 测评结果:AC
  • 用时:728ms
  • 内存:3976kb
  • [2023-09-10 20:49:49]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

vector<string> v = {
        "NNRKR",
        "NRNKR",
        "NRKNR",
        "NRKRN",
        "RNNKR",
        "RNKNR",
        "RNKRN",
        "RKNNR",
        "RKNRN",
        "RKRNN"
};

vector<string> fi;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (int i = 0; i < 8; i += 2) {
        for (int j = 1; j < 8; j += 2) {
            for (int k = 0; k < 6; ++k) {
                for (int l = 0; l < v.size(); ++l) {
                    string s(8, '.');
                    s[i] = s[j] = 'B';
                    int idx = 0;
                    for (int m = 0; m < 8; ++m) {
                        if (s[m] == '.') {
                            if (idx == k) {
                                s[m] = 'Q';
                            }
                            idx += 1;
                        }
                    }
                    idx = 0;
                    for (int m = 0; m < 8; ++m) {
                        if (s[m] == '.') {
                            s[m] = v[l][idx];
                            idx += 1;
                        }
                    }
                    fi.push_back(s);
                }
            }
        }
    }

    auto check = [](string s,string t) -> int {
        int res = 0;
        for (int i = 0; i < 8; ++i) {
            res += (s[i] == t[i]);
        }
        return res;
    };

    auto query = [](string s, int id = -1) -> int {
        int v = 0;
        if (id == -1) cin >> v;
        else {
            for (int i = 0; i < 8; ++i) {
                v += (s[i] == fi[id][i]);
            }
        }
        return v;
    };

    vector<vector<string>> base(9);
    for (int i = 0; i < fi.size(); ++i) {
        base[check(fi[341], fi[i])].push_back(fi[i]);
    }

    while (1) {
        string s; cin >> s;
        if (s == "END") break;
        cin >> s;
        
        cout << fi[341] << endl;
        int r = query(fi[341]);
        if (r == 8) continue;
        auto kouho = base[r];

        while (1) {
            int mx = 960;
            int opt = -1;
            vector<vector<string>> opt_cnt;
            for (int i = 0; i < fi.size(); ++i) {
                vector<vector<string>> cnt(9);
                for (auto j : kouho) {
                    cnt[check(fi[i], j)].push_back(j);
                }
                int u = 0;
                for (int j = 0; j < 9; ++j) {
                    if (cnt[j].size() > cnt[u].size()) u = j;
                }
                if (mx > cnt[u].size()) {
                    mx = cnt[u].size();
                    opt = i;
                    opt_cnt = cnt;
                }
            }
            cout << fi[opt] << endl;
            int rui = query(fi[opt]);
            kouho = opt_cnt[rui];
            if (rui == 8) break;
            if (kouho.size() == 1) {
                cout << kouho[0] << endl;
                rui = query(kouho[0]);
                if (rui == 8) break;
            }
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 3776kb

input:

GAME 1
1
0
3
4
0
8
END

output:

NRBBNKQR
BRNNKBQR
NQRKBRNB
RQBBKRNN
BBQNNRKR
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 707ms
memory: 3812kb

input:

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

output:

NRBBNKQR
BRNNKBQR
NQRKBRNB
RQBBKRNN
BBQNNRKR
RKRBBQNN
NRBBNKQR
RNBBQKRN
RQKBNNBR
BBRNNQKR
BBQNNRKR
RKRBBNQN
NRBBNKQR
BRNNKBQR
NQRKBRNB
RQBBKRNN
BBQNRKNR
RKRBBNNQ
NRBBNKQR
BRNNKBQR
NQRKBRNB
QNRBBKRN
BBQNNRKR
RKRBQNBN
NRBBNKQR
RNBBQKRN
RQKBNNBR
QNRBBKNR
RKRBNQBN
NRBBNKQR
RNBBQKRN
RKBBRNNQ
BBQNRKNR
RKR...

result:

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

Test #3:

score: 0
Accepted
time: 728ms
memory: 3756kb

input:

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

output:

NRBBNKQR
RNBBQKRN
RKBBRNNQ
BBQNRKNR
RKQBBNNR
NRBBNKQR
RNBBQKRN
RKBBRNNQ
BBRKQNNR
RKNBBQNR
NRBBNKQR
RBBNQKRN
BQNBRNKR
BRKRNNQB
RKNBBNQR
NRBBNKQR
RBBNQKRN
BQNBRNKR
BBRNKNRQ
BBQNNRKR
RKQBNNBR
NRBBNKQR
RNBBQKRN
RQKBNNBR
BBQNRNKR
RKNBQNBR
NRBBNKQR
RBBNQKRN
BQNBRNKR
BBRNKNRQ
BBQNRNKR
RKNBNQBR
NRBBNKQR
BRN...

result:

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

Test #4:

score: 0
Accepted
time: 724ms
memory: 3812kb

input:

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

output:

NRBBNKQR
BRNNKBQR
BNRBKRQN
BRKQNBNR
BBQNNRKR
QRKRBBNN
NRBBNKQR
RBBNQKRN
BQNBRNKR
BNQRKRNB
NRKRBBQN
NRBBNKQR
RNBBQKRN
BRKQNRNB
BBQNNRKR
NRKRBBNQ
NRBBNKQR
BRNNKBQR
RKQNRBBN
BBRNQNKR
BBQNRKNR
QRKRBNNB
NRBBNKQR
RNBBQKRN
BRKQNRNB
BBNQRNKR
BBQNNRKR
NRKRBQNB
NRBBNKQR
RBBNQKRN
BNRBQNKR
BBNQNRKR
NRKRBNQB
NRB...

result:

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

Test #5:

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

input:

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

output:

NRBBNKQR
RKNNRQBB
RBNKBNRQ
BNRKRBQN
RQNKRBBN
NRBBNKQR
RKNNRQBB
BQRNKRNB
RBKNRNBQ
RNQKRBBN
NRBBNKQR
RKNNRQBB
RBNKBNRQ
BBQNRNKR
RNNKRBBQ
NRBBNKQR
RKNNRQBB
BBNRKQRN
BBQNNRKR
RQNKRNBB
NRBBNKQR
RKNNRQBB
RBNKBNRQ
BNRKRBQN
RNQKRNBB
NRBBNKQR
RKNNRQBB
BNRKRBQN
RNNKRQBB
NRBBNKQR
BRNNKBQR
NQRKBRNB
RQBBKRNN
BBN...

result:

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

Test #6:

score: 0
Accepted
time: 718ms
memory: 3764kb

input:

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

output:

NRBBNKQR
RBBNQKRN
BBQRNKNR
BBNRQKRN
BBQNNRKR
QRBKNBRN
NRBBNKQR
RBBNQKRN
BBNNRQKR
BBNQRKNR
NRBKQBRN
NRBBNKQR
BQNBRKNR
BBNRNQKR
NRBKNBRQ
NRBBNKQR
RBBNQKRN
BBQNRKNR
RNBKNBRQ
QRBKNNRB
NRBBNKQR
RBBNQKRN
BBQRNKNR
BBRNKNRQ
BBQNRNKR
NRBKQNRB
NRBBNKQR
BQNBRKNR
BBNRNQKR
NRBKNQRB
NRBBNKQR
BRNNKBQR
RBQNBNKR
BBR...

result:

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

Test #7:

score: 0
Accepted
time: 726ms
memory: 3852kb

input:

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

output:

NRBBNKQR
BRNNKBQR
RKQNRBBN
BBRQNKRN
BBQNNRKR
RBBQKRNN
NRBBNKQR
RNBBQKRN
RQKBNNBR
BBQRNKRN
BBQNNRKR
RBBNKRQN
NRBBNKQR
BRNNKBQR
BNRBKRQN
BBQNRKRN
BBQNRNKR
RBBNKRNQ
NRBBNKQR
RKNNRQBB
BQRNKRNB
RBQNBKRN
RBQNKRBN
NRBBNKQR
RKNNRQBB
BQRNKRNB
RKNRBBNQ
RBNQKRBN
NRBBNKQR
RKNNRQBB
RBNKBNRQ
BBQNRNKR
RBNNKRBQ
NRB...

result:

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

Test #8:

score: 0
Accepted
time: 714ms
memory: 3884kb

input:

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

output:

NRBBNKQR
RBBNQKRN
BNRBQNKR
BQNBNRKR
QRNBKNBR
NRBBNKQR
BQNBRKNR
BRQBKNNR
NRQBKNBR
NRBBNKQR
BQNBRKNR
BBQRNKNR
BBNRKQNR
NRNBKQBR
NRBBNKQR
RNBBQKRN
BRKQNRNB
BBRQKNNR
BBQNNRKR
QRNNKBBR
NRBBNKQR
RBBNQKRN
BQNBRNKR
BBRNNQKR
BBQNNRKR
NRQNKBBR
NRBBNKQR
RBBNQKRN
BNRBQNKR
BBNQNRKR
BBQNNRKR
NRNQKBBR
NRBBNKQR
RKN...

result:

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

Test #9:

score: 0
Accepted
time: 565ms
memory: 3800kb

input:

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

output:

NRBBNKQR
RNBBQKRN
NRNKBRQB
BBRKRNNQ
BBQNNRKR
QBBRKNNR
NRBBNKQR
RBBNQKRN
BBQNRKNR
NBBRQNKR
NBBRKQNR
NRBBNKQR
BQNBRKNR
BNQRNBKR
BBQRKNNR
NBBRKNQR
NRBBNKQR
BRNNKBQR
RBQNBNKR
BBNQRNKR
QBNRKNBR
NRBBNKQR
RNBBQKRN
BRKQNRNB
BQRNNBKR
BBQNNRKR
NBQRKNBR
NRBBNKQR
RNBBQKRN
BRKQNRNB
BQRNNBKR
BBQNNRKR
NBNRKQBR
NRB...

result:

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

Test #10:

score: 0
Accepted
time: 593ms
memory: 3812kb

input:

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

output:

NRBBNKQR
RBBNQKRN
BBQNRKNR
BBQNNRKR
BBRQNKNR
NRBBNKQR
RNBBQKRN
RKBBRNNQ
BBQNRKNR
BBRNQKNR
NRBBNKQR
BQNBRKNR
BBQRNKNR
BBQNNRKR
BBRNNKQR
NRBBNKQR
BQNBRKNR
BBQRNKNR
BQRBNKNR
NRBBNKQR
RBBNQKRN
BBQNRKNR
BBNQNRKR
BNRBQKNR
NRBBNKQR
BQRBNNKR
NQBBRNKR
BNRBNKQR
NRBBNKQR
RNBBQKRN
NRNKBRQB
BBNQRKNR
BBQNRNKR
QBR...

result:

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

Test #11:

score: 0
Accepted
time: 690ms
memory: 3976kb

input:

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

output:

NRBBNKQR
RNBBQKRN
RKBBRNNQ
BQNBNRKR
RQNBBNKR
NRBBNKQR
RNBBQKRN
RQKBNNBR
QNRBBKNR
RNQBBNKR
NRBBNKQR
RNBBQKRN
RQKBNNBR
BBRNNQKR
BBQNNRKR
RNNBBQKR
NRBBNKQR
BRNNKBQR
QNBNRBKR
BBNQNRKR
RQNNBBKR
NRBBNKQR
BRNNKBQR
RBQNBNKR
BBNQRNKR
RNQNBBKR
NRBBNKQR
BRNNKBQR
RBQNBNKR
BBQNRNKR
BBQNRKNR
RNNQBBKR
NRBBNKQR
BQN...

result:

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

Extra Test:

score: 0
Extra Test Passed