QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#165493#7179. Fischer's Chess Guessing Gameucup-team1600#AC ✓50ms4644kbC++235.4kb2023-09-05 18:49:332023-09-05 18:49:35

Judging History

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

  • [2023-09-05 18:49:35]
  • 评测
  • 测评结果:AC
  • 用时:50ms
  • 内存:4644kb
  • [2023-09-05 18:49:33]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef LOCAL
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
inline bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
inline bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL

const int max_n = -1, inf = 1000111222;

mt19937 rng(228);
template<typename T = int>
inline T randll(T l = INT_MIN, T r = INT_MAX) {
    return uniform_int_distribution<T>(l, r)(rng);
}

inline ld randld(ld l = INT_MIN, ld r = INT_MAX) {
    return uniform_real_distribution<ld>(l, r)(rng);
}

int MX = 0;

map <set <string>, string> to_ask;

inline int rec (vector <string> have, int d = 1, bool gg = true) {
    if (have.empty()) {
        return d - 1;
    }
//    LOG(d);
    umax(MX, d);
    int mx = inf;
    vector <int> can;
//    shuffle(all(have), rng);
    int y = 0;
    for (int i = 0; i < len(have); i++) {
        int cnt[9] = {};
        for (auto &j : have) {
            int cur = 0;
            for (int k = 0; k < 8; k++) {
                if (have[i][k] == j[k]) {
                    ++cur;
                }
            }
            ++cnt[cur];
        }
        int val = 0;
        for (int j = 0; j < 8; j++) {
            umax(val, cnt[j]);
        }
        if (umin(mx, val)) {
            y = 0;
            can.clear();
        }
        if (mx == val) {
            ++y;
            can.pb(i);
        }
    }
    int res = inf;
    LOG(len(can));
    int best = -1;
    for (int pos : can) {
        vector<string> nice[9];
        for (auto &j: have) {
            int cur = 0;
            for (int k = 0; k < 8; k++) {
                if (have[pos][k] == j[k]) {
                    ++cur;
                }
            }
            nice[cur].pb(j);
        }
        int cur = 0;
        for (int j = 0; j < 8; j++) {
            umax(cur, rec(nice[j], d + 1, false));
        }
        if (umin(res, cur)) {
            best = pos;
        }
    }
    if (gg) {
        int pos = best;
        vector<string> nice[9];
        for (auto &j: have) {
            int cur = 0;
            for (int k = 0; k < 8; k++) {
                if (have[pos][k] == j[k]) {
                    ++cur;
                }
            }
            nice[cur].pb(j);
        }
        for (int j = 0; j < 8; j++) {
            rec(nice[j], d + 1, true);
        }
        set <string> s(all(have));
        assert(!to_ask.count(s));
        to_ask[s] = have[pos];
    }
    return res;
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string s = "RQKBBNRN";
    sort(all(s));
    vector <string> can;
    do {
        bool ok = true;
        map <char, vector <int> > have;
        for (int i = 0; i < 8; i++) {
            have[s[i]].pb(i);
        }
        if ((have['B'][0] ^ have['B'][1]) % 2 == 0) {
            ok = false;
        }
        if (have['K'][0] < have['R'][0] || have['K'][0] > have['R'][1]) {
            ok = false;
        }
        if (ok) {
            can.pb(s);
        }
    } while (next_permutation(all(s)));
//    LOG(len(can));
//    LOG(rec(can));
//    LOG(MX);
    rec(can);
    string game;
    int num;
    while (cin >> game) {
        if (game == "END") {
            break;
        }
        cin >> num;
        set<string> cur(all(can));
        while (true) {
            string A = to_ask[cur];
            cout << A << endl;
            int res;
            cin >> res;
            if (res == 8) {
                break;
            }
            set <string> new_cur;
            for (auto &j : cur) {
                int cc = 0;
                for (int k = 0; k < 8; k++) {
                    if (A[k] == j[k]) {
                        ++cc;
                    }
                }
                if (cc == res) {
                    new_cur.insert(j);
                }
            }
            cur.swap(new_cur);
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 35ms
memory: 4308kb

input:

GAME 1
1
2
2
1
2
8
END

output:

NRBBNKQR
BNRKQBNR
RNBQKRNB
BRNQKBRN
QNRNBKRB
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 46ms
memory: 4376kb

input:

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

output:

NRBBNKQR
BNRKQBNR
RNBQKRNB
BRNQKBRN
QNRNBKRB
RKRBBQNN
NRBBNKQR
RBBNKQNR
QRKNNRBB
NBNRBKRQ
BQNBRNKR
RKRBBNQN
NRBBNKQR
BNRKQBNR
RNBQKRNB
BRNQKBRN
RBKNBQNR
RKRBBNNQ
NRBBNKQR
BNRKQBNR
RNBQKRNB
BBNQRNKR
QBRKNRBN
RKRBQNBN
NRBBNKQR
RBBNKQNR
NBNQBRKR
BRKBRQNN
QRBKRNNB
RKRBNQBN
NRBBNKQR
RBBNKQNR
QRKNNRBB
NRK...

result:

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

Test #3:

score: 0
Accepted
time: 47ms
memory: 4348kb

input:

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

output:

NRBBNKQR
RBBNKQNR
RKBNNBRQ
BRKNQBNR
RBKQNNBR
RKQBBNNR
NRBBNKQR
RBBNKQNR
BBRNNQKR
RKNBBQNR
NRBBNKQR
NRBQKBRN
RBNNBKQR
RBQNNKBR
RKNBBNQR
NRBBNKQR
NRBQKBRN
RBNNBKQR
BNRBQKNR
RKQBNNBR
NRBBNKQR
RBBNKQNR
NBNQBRKR
BRNNKRQB
NNQRKBBR
RKNBQNBR
NRBBNKQR
NRBQKBRN
RBNNBKQR
BBQRNKNR
QNNBRKBR
RKNBNQBR
NRBBNKQR
BNR...

result:

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

Test #4:

score: 0
Accepted
time: 45ms
memory: 4408kb

input:

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

output:

NRBBNKQR
BNRKQBNR
RNBQKRNB
BBNQRNKR
QRKRBBNN
NRBBNKQR
NRBQKBRN
NBBRQKRN
NRKBBQRN
NRKRBBQN
NRBBNKQR
RBBNKQNR
QRKNNRBB
NRKRBBNQ
NRBBNKQR
BNRKQBNR
RNKQNRBB
QNBRKNRB
QRKRBNNB
NRBBNKQR
RBBNKQNR
NBNQBRKR
BRNNKRQB
BQRNNBKR
NRKRBQNB
NRBBNKQR
NRBQKBRN
BRKBNNRQ
BRNBKQNR
NNRBBKRQ
NRKRBNQB
NRBBNKQR
RBBNKQNR
NRK...

result:

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

Test #5:

score: 0
Accepted
time: 50ms
memory: 4400kb

input:

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

output:

NRBBNKQR
RKNNRQBB
RBKNRNBQ
RKNNBBRQ
RQNKRBBN
NRBBNKQR
RKNNRQBB
RBKNQRBN
RNQKRBBN
NRBBNKQR
RKNNRQBB
RBKNRNBQ
RNKNQRBB
RNNKRBBQ
NRBBNKQR
RKNNRQBB
RKNRQNBB
RKNRBQNB
RQNKRNBB
NRBBNKQR
RKNNRQBB
RBKNRNBQ
RNKNQRBB
RNQKRNBB
NRBBNKQR
RKNNRQBB
RKNNRBBQ
RNKNRQBB
RNNKRQBB
NRBBNKQR
BNRKQBNR
BQRKNNRB
BBNNQRKR
RBB...

result:

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

Test #6:

score: 0
Accepted
time: 39ms
memory: 4612kb

input:

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

output:

NRBBNKQR
NRBQKBRN
NRBQKRNB
QRBKNBRN
NRBBNKQR
NRBQKBRN
NRBKQBRN
NRBBNKQR
RNBKNBQR
RKBBNQNR
BRKNNBQR
NRBKNBRQ
NRBBNKQR
NRBQKBRN
RNBBQKRN
NRQNBKRB
NRBKQRNB
QRBKNNRB
NRBBNKQR
NRBQKBRN
NBBRQKRN
NNBQRKRB
NRBKQNRB
NRBBNKQR
RNBKNBQR
NBBRKNQR
BNNBRKQR
NRBKNQRB
NRBBNKQR
BNRKQBNR
RNBQKRNB
NBRKBNRQ
QRNKBBRN
NRB...

result:

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

Test #7:

score: 0
Accepted
time: 45ms
memory: 4568kb

input:

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

output:

NRBBNKQR
BNRKQBNR
RNKQNRBB
RBBQKRNN
NRBBNKQR
RBBNKQNR
RBBKQNNR
RBBNKRQN
NRBBNKQR
BNRKQBNR
RNKQNRBB
QNBRKNRB
RBQNKNBR
RBBNKRNQ
NRBBNKQR
RKNNRQBB
RBKNQRBN
RBNKQRBN
RBQNKRBN
NRBBNKQR
RKNNRQBB
RBKNQRBN
RBKNBQRN
RBNQKRBN
NRBBNKQR
RKNNRQBB
RBKNRNBQ
RBNNKRBQ
NRBBNKQR
RBBNKQNR
BBRNNQKR
RNBBKRNQ
RQBBKRNN
NRB...

result:

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

Test #8:

score: 0
Accepted
time: 49ms
memory: 4644kb

input:

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

output:

NRBBNKQR
NRBQKBRN
BRKBNNRQ
BRNBKQNR
QRNBKNBR
NRBBNKQR
RNBKNBQR
QRNBBKNR
NRKBQNBR
NRQBKNBR
NRBBNKQR
RNBKNBQR
QRNBBKNR
NRNBKQBR
NRBBNKQR
RBBNKQNR
RKBNNBRQ
BRKNQBNR
BNRNKBQR
QRNNKBBR
NRBBNKQR
NRBQKBRN
NBBRQKRN
NRNQBBKR
NRQNKBBR
NRBBNKQR
NRBQKBRN
NRBQKRNB
NRNQKBBR
NRBBNKQR
RKNNRQBB
BBQRKRNN
BBQRKNRN
BBR...

result:

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

Test #9:

score: 0
Accepted
time: 43ms
memory: 4308kb

input:

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

output:

NRBBNKQR
RBBNKQNR
RBBKQNNR
QBBRKNNR
NRBBNKQR
NRBQKBRN
RNBBQKRN
NBBQRNKR
NBBRKQNR
NRBBNKQR
RNBKNBQR
NBBRKNQR
NRBBNKQR
BNRKQBNR
RNKQNRBB
BRQNKNRB
BBNQRKRN
QBNRKNBR
NRBBNKQR
RBBNKQNR
RKBNNBRQ
BBNRQKNR
BQRBKNNR
NBQRKNBR
NRBBNKQR
RBBNKQNR
BBRNNQKR
RKBNNQRB
BRQNKBNR
NBNRKQBR
NRBBNKQR
RBBNKQNR
BBRNNQKR
QNB...

result:

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

Test #10:

score: 0
Accepted
time: 48ms
memory: 4352kb

input:

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

output:

NRBBNKQR
NRBQKBRN
NNRBBQKR
NBQNRKBR
BBRQNKNR
NRBBNKQR
RBBNKQNR
BBRNNQKR
BBRNKNQR
BBRNQKNR
NRBBNKQR
RNBKNBQR
NBBRKNQR
NNBBQRKR
BBRNNKQR
NRBBNKQR
RNBKNBQR
NBBRQKNR
NNQBRKBR
BQRBNKNR
NRBBNKQR
NRBQKBRN
RBNNBKQR
BNRBQKNR
NRBBNKQR
BNRBNKQR
NRBBNKQR
RBBNKQNR
BBRNNQKR
BBQNRKNR
QBRNBKNR
NRBBNKQR
NRBQKBRN
BRK...

result:

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

Test #11:

score: 0
Accepted
time: 41ms
memory: 4336kb

input:

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

output:

NRBBNKQR
RBBNKQNR
NBNQBRKR
NQRNBBKR
RQNBBNKR
NRBBNKQR
RBBNKQNR
NBNQBRKR
BNNBRQKR
BRNNQBKR
RNQBBNKR
NRBBNKQR
RBBNKQNR
RKBNNBRQ
RQNBKNBR
RBNKBNQR
RNNBBQKR
NRBBNKQR
BNRKQBNR
RNBQKRNB
BBNQRNKR
QBRNKNBR
RQNNBBKR
NRBBNKQR
BNRKQBNR
BQRKNNRB
QNNRKBBR
RKNQBBNR
RNQNBBKR
NRBBNKQR
BNRKQBNR
BQRKNNRB
QNNRKBBR
RKN...

result:

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

Extra Test:

score: 0
Extra Test Passed