QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#196943#7179. Fischer's Chess Guessing Gameucup-team1430AC ✓702ms4180kbC++202.7kb2023-10-02 04:47:522023-10-02 04:47:53

Judging History

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

  • [2023-10-02 04:47:53]
  • 评测
  • 测评结果:AC
  • 用时:702ms
  • 内存:4180kb
  • [2023-10-02 04:47:52]
  • 提交

answer

#include <bits/stdc++.h>

#define ff first
#define ss second
#define ll long long
#define ld long double
#define pb push_back
#define endl '\n'
#define sws cin.tie(0)->sync_with_stdio(false);

const int N = 0;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;

using namespace std;

bool is_valid(vector<char> s) {
    int n = s.size();
    bool ok = true;
    int bishop = -1, rook = -1;
    for (int i=0;i<n;i++) {
        auto c = s[i];
        if (c == 'B') {
            if (bishop == -1) bishop = i;
            else ok &= ((i - bishop) % 2 == 1);
        } else if (c == 'R') {
            if (rook == -1) rook = i;
            else rook = -1;
        } else if (c == 'K') {
            ok &= (rook != -1);
        }
    }

    return ok;
}

auto dist = [](vector<char> &a, vector<char> &b) {
    int qnt = 0;
    int n = a.size();
    for (int i=0;i<n;i++) {
        if (a[i] != b[i]) qnt ++;
    }
    return qnt;
};

void solve() {


    vector<char> pos = {'K', 'Q', 'R', 'R', 'N', 'N', 'B', 'B'};
    sort(pos.begin(), pos.end());
    vector<vector<char>> p_ini;
    do {
        p_ini.push_back(pos);
    } while (next_permutation(pos.begin(), pos.end()));

    vector<vector<char>> p;
    for (auto pi: p_ini) if (is_valid(pi)) p.push_back(pi);
    p_ini = p;

    auto print = [&](vector<char> &x) {
        for (auto c: x) cout << c;
        cout << endl;
    };


    auto choose = [&](vector<vector<char>> &p) {
        int n = p_ini.size();
        int m = p.size();
        int id = 0, mx = INF;
        for (int i=0;i<n;i++) {
            vector<int> dists(10, 0);
            for (int j=0;j<m;j++) {
                int d = dist(p_ini[i], p[j]);
                dists[d] ++;
            }
            int dmax = 0;
            for (auto d: dists) dmax = max(dmax, d);
            if (dmax <= mx) {
                id = i; mx = dmax;
            }
        }

        return id;
    };


    int it = 6;
    while (it --) {
        if (p.size() == 1) {
            print(p[0]); cout.flush();
            int x; cin >> x; assert(x == 8);
            return;
        }
        int id = choose(p);
        print(p_ini[id]);
        cout.flush();
        int x; cin >> x;
        if (x == 8) { return; }

        vector<vector<char>> p2;

        for (auto pi: p) {
            if (dist(p_ini[id], pi) == 8 - x) {
                p2.push_back(pi);
            }
        }

        swap(p, p2);
    }
}

int main() {
    #ifndef LOCAL
        sws;
    #endif

    string s; int t;
    while (cin >> s >> t) {
        if (s == "END") return 0;
        solve();
    }


    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 3820kb

input:

GAME 1
3
1
4
1
1
8
END

output:

RQKNBBRN
NRNKBBQR
RKBRNQNB
RQNKNBBR
RQNNKRBB
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 669ms
memory: 3920kb

input:

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

output:

RQKNBBRN
NRNKBBQR
RKBRNQNB
RQNKNBBR
RQNNKRBB
RKRBBQNN
RQKNBBRN
NRNKBBQR
RNQKBNRB
RQNNKBBR
RQNNKRBB
RKRBBNQN
RQKNBBRN
NRKQBBNR
RNBQKBNR
RQNKBRNB
RQNNKRBB
RKRBBNNQ
RQKNBBRN
NRKQBBNR
BNRNQKRB
RQKNRNBB
RQNNKRBB
RKRBQNBN
RQKNBBRN
NRKQBBNR
BNRNQKRB
RNNKQRBB
RQNNKRBB
RKRBNQBN
RQKNBBRN
RQBKNNRB
RKNBNQBR
RQN...

result:

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

Test #3:

score: 0
Accepted
time: 631ms
memory: 3880kb

input:

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

output:

RQKNBBRN
NRKQBBNR
RBNNBKQR
RNNQKBBR
RQNNKRBB
RKQBBNNR
RQKNBBRN
NRKQBBNR
RBNNBKQR
RNKBBRNQ
RKNBBQNR
RQKNBBRN
NRKQBBNR
RNBQKBNR
RQNKBRNB
RQNNKRBB
RKNBBNQR
RQKNBBRN
RQBKNNRB
RKNBNQBR
RQNNKRBB
RKQBNNBR
RQKNBBRN
RQBKNNRB
RQNBNKBR
RQNKRNBB
RKNBQNBR
RQKNBBRN
RQBKNNRB
RQNBNKBR
RNNQBKRB
RKNBNQBR
RQKNBBRN
RQB...

result:

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

Test #4:

score: 0
Accepted
time: 659ms
memory: 4028kb

input:

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

output:

RQKNBBRN
RQBNKBNR
RNNKBQRB
RQNKRBBN
QRKRBBNN
RQKNBBRN
RQBNKBNR
RQNBBKRN
RQBNKNRB
NRKRBBQN
RQKNBBRN
NRNKBBQR
RQNKBBNR
RQNKRNBB
NRKRBBNQ
RQKNBBRN
NRKQBBNR
RQBNKBNR
RQNNKBBR
QRKRBNNB
RQKNBBRN
NRKQBBNR
RQNNKBBR
RQNNBKRB
NRKRBQNB
RQKNBBRN
NRKQBBNR
RQBNKBNR
RQNNKRBB
NRKRBNQB
RQKNBBRN
NRNKBBQR
RNQKBNRB
QRK...

result:

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

Test #5:

score: 0
Accepted
time: 673ms
memory: 4000kb

input:

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

output:

RQKNBBRN
RQBNKBNR
RKBRQBNN
RQNKRBBN
RQKNBBRN
NRNKBBQR
RNQKBNRB
RQNBBNKR
RQNNKRBB
RNQKRBBN
RQKNBBRN
NRKQBBNR
RBBQKNNR
RQKRNBBN
RQNNKRBB
RNNKRBBQ
RQKNBBRN
NRKQBBNR
BNRNQKRB
RNNKQRBB
RQNNKRBB
RQNKRNBB
RQKNBBRN
RQBKNNRB
RKBRNBNQ
RNQKNRBB
RNQKRNBB
RQKNBBRN
RQBKNNRB
RKNBNQBR
RQNKRNBB
RQNKRBBN
RNNKRQBB
RQK...

result:

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

Test #6:

score: 0
Accepted
time: 689ms
memory: 4152kb

input:

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

output:

RQKNBBRN
NRNKBBQR
RNNQBKRB
RQNNKBBR
RQBNNKRB
QRBKNBRN
RQKNBBRN
NRNKBBQR
RQNKBBNR
RQNNKRBB
NRBKQBRN
RQKNBBRN
NRKQBBNR
RBNNBKQR
RQNBKRBN
RQNNKRBB
NRBKNBRQ
RQKNBBRN
RQBKNNRB
QRBKNNRB
RQKNBBRN
RQBKNNRB
RQBNNBKR
RQNKNRBB
NRBKQNRB
RQKNBBRN
RQBKNNRB
RQBNNBKR
RQNNKRBB
NRBKNQRB
RQKNBBRN
RQBNKBNR
RQNBBKRN
RNQ...

result:

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

Test #7:

score: 0
Accepted
time: 685ms
memory: 4112kb

input:

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

output:

RQKNBBRN
NRKQBBNR
RNBQKBNR
RBQNKNBR
RBBQKRNN
RQKNBBRN
NRNKBBQR
RKBRNQNB
RQNNKRBB
RBBNKRQN
RQKNBBRN
NRKQBBNR
RBBQKNNR
RQNNBBKR
RBBNKRNQ
RQKNBBRN
NRNKBBQR
RNKRQNBB
RQNNKRBB
RBQNKRBN
RQKNBBRN
NRKQBBNR
RBBQKNNR
RQNBNKBR
RQNNKRBB
RBNQKRBN
RQKNBBRN
NRKQBBNR
BNRNQKRB
RNNKQRBB
RQNNKRBB
RBNNKRBQ
RQKNBBRN
NRN...

result:

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

Test #8:

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

input:

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

output:

RQKNBBRN
BBQRNNKR
RNBBNKQR
NRNBBQKR
QRNBKNBR
RQKNBBRN
BBQRNNKR
RNNBBKQR
RQNKRNBB
RQNNKRBB
NRQBKNBR
RQKNBBRN
BBQRNNKR
BRQKNRNB
RQNNKRBB
NRNBKQBR
RQKNBBRN
NRKQBBNR
RBNNBKQR
RNNQKBBR
QRNNKBBR
RQKNBBRN
NRKQBBNR
RQBNKBNR
RQNNKRBB
NRQNKBBR
RQKNBBRN
RQBKNNRB
RBQNKRBN
NNRQKBBR
NRNQKBBR
RQKNBBRN
RQBKNNRB
RBQ...

result:

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

Test #9:

score: 0
Accepted
time: 675ms
memory: 4112kb

input:

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

output:

RQKNBBRN
BBQRNNKR
QRNBNKBR
RBNKNQBR
QBBRKNNR
RQKNBBRN
BBQRNNKR
RNNBBKQR
RBKNQNBR
NBBRKQNR
RQKNBBRN
BBQRNNKR
QRNBNKBR
RKRQBNNB
NBBRKNQR
RQKNBBRN
BBQRNNKR
QRNBNKBR
RQNBKRBN
QBNRKNBR
RQKNBBRN
BBQRNNKR
RNQKNBBR
RQNKNRBB
NBQRKNBR
RQKNBBRN
BBQRNNKR
RNNBBKQR
RQNKRNBB
RQNNKRBB
NBNRKQBR
RQKNBBRN
RQBKNNRB
NBB...

result:

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

Test #10:

score: 0
Accepted
time: 678ms
memory: 3952kb

input:

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

output:

RQKNBBRN
BBQRNNKR
QRNBNKBR
RBBNNKRQ
BBRQNKNR
RQKNBBRN
RQBKNNRB
RBQNKRBN
NNRQKBBR
RQNNKRBB
BBRNQKNR
RQKNBBRN
RQBKNNRB
NBBRNQKR
RKBQNBNR
RQNNKBBR
BBRNNKQR
RQKNBBRN
RQBKNNRB
RQNBNKBR
RQNKRNBB
BQRBNKNR
RQKNBBRN
BBQRNNKR
RNBBNKQR
NNBQRBKR
BNRBQKNR
RQKNBBRN
BBQRNNKR
RNNBBKQR
RQNNKRBB
BNRBNKQR
RQKNBBRN
NRK...

result:

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

Test #11:

score: 0
Accepted
time: 667ms
memory: 4180kb

input:

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

output:

RQKNBBRN
NRNKBBQR
RNNQBKRB
RQNNKBBR
RQNKRNBB
RQNBBNKR
RQKNBBRN
NRKQBBNR
RNBQKBNR
RQKRNNBB
RQNNKRBB
RNQBBNKR
RQKNBBRN
NRKQBBNR
RNBQKBNR
RQKRNNBB
RQNNBKRB
RNNBBQKR
RQKNBBRN
RKNNBRQB
RQNNKBBR
RQNNBBKR
RQKNBBRN
RQBNKBNR
RQKNBRNB
RNNKBRQB
RNQNBBKR
RQKNBBRN
NRNKBBQR
RQNKBBNR
RNNQBBKR
RQKNBBRN
BBQRNNKR
RQB...

result:

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

Extra Test:

score: 0
Extra Test Passed