QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#176262#7179. Fischer's Chess Guessing GameHaccerKatAC ✓1663ms4064kbC++206.3kb2023-09-11 13:59:352023-09-11 13:59:36

Judging History

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

  • [2023-09-11 13:59:36]
  • 评测
  • 测评结果:AC
  • 用时:1663ms
  • 内存:4064kb
  • [2023-09-11 13:59:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
    return t.size();
}

template<typename T, size_t N>
int SIZE(T (&t)[N]){
    return N;
}

string to_string(char t){
    return "'" + string({t}) + "'";
}

string to_string(bool t){
    return t ? "true" : "false";
}

string to_string(const string &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += t[i];
    }
    return '"' + ret + '"';
}

string to_string(const char* t){
    string ret(t);
    return to_string(ret);
}

template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
        ret += t[i] + '0';
    }
    return to_string(ret);
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);

template<typename T, typename S>
string to_string(const pair<T, S> &t){
    return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
    string ret = "[";
    x1 = min(x1, SIZE(t));
    auto e = begin(t);
    advance(e,x1);
    for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += to_string(*e, C...) + (i != _i ? ", " : "");
        e = next(e);
    }
    return ret + "]";
}

template<int Index, typename... Ts>
struct print_tuple{
    string operator() (const tuple<Ts...>& t) {
        string ret = print_tuple<Index - 1, Ts...>{}(t);
        ret += (Index ? ", " : "");
        return ret + to_string(get<Index>(t));
    }
};

template<typename... Ts>
struct print_tuple<0, Ts...> {
    string operator() (const tuple<Ts...>& t) {
        return to_string(get<0>(t));
    }
};

template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
    const auto Size = tuple_size<tuple<Ts...>>::value;
    return print_tuple<Size - 1, Ts...>{}(t);
}

void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
    cout << to_string(H) << " | ";
    dbgr(T...);
}

void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
    cout << H << " ";
    dbgs(T...);
}

/*
formatted functions:
*/

/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;

#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)

/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;

#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 200005;
const int X = 960;
const int LOG = 20;
const int inf = 1e9;
const double eps = 1e-11;
char c[5] = {'K', 'R', 'B', 'N', 'Q'};
int idx = 0;
vector<vector<int>> positions(X);
void dfs(vector<int> a, int p = 0) {
    if (p == 5) {
        positions[idx++] = a;
        return;
    }
    
    if (p == 0 || p == 4) {
        for (int i = 0; i < 8; i++) {
            if (a[i] != -1 || (p == 0 && (i == 0 || i == 7))) continue;
            vector<int> b = a;
            b[i] = p;
            dfs(b, p + 1);
        }
    }
    
    else {
        int kp = -1;
        for (int i = 0; i < 8; i++) {
            if (a[i] == 0) kp = i;
        }
        
        for (int i = 0; i < 8; i++) {
            for (int j = i + 1; j < 8; j++) {
                if (a[i] != -1 || a[j] != -1) continue;
                vector<int> b = a;
                bool ok = 0;
                if (p == 1 && i < kp && j > kp) b[i] = b[j] = p, ok = 1;
                if (p == 2 && (i & 1) != (j & 1)) b[i] = b[j] = p, ok = 1;
                if (p == 3) b[i] = b[j] = p, ok = 1;
                if (ok) dfs(b, p + 1);
            }
        }
    }
}

int query(vector<int> a) {
    for (int i = 0; i < 8; i++) {
        cout << c[a[i]];
    }
    
    cout << endl;
    int x;
    cin >> x;
    return x;
}

int n, m, k, qq;
void solve() {
    vector<vector<int>> cand = positions;
    vector<int> test = {1, 3, 2, 4, 0, 2, 3, 1};
    while (true) {
        if (cand.size() == 1) {
            query(cand[0]);
            break;    
        }
        
        vector<int> best;
        int val = inf;
        for (auto a : positions) {
            vector<int> cnt(9);
            for (auto b : cand) {
                int x = 0;
                for (int i = 0; i < 8; i++) {
                    x += a[i] == b[i];
                }
                
                cnt[x]++;
            }
            
            int mx = 0;
            for (int i = 0; i <= 8; i++) mx = max(mx, cnt[i]);
            if (mx < val) val = mx, best = a;
        }
        
        vector<vector<int>> ncand;
        int x = query(best);
        if (x == 8) break;
        for (auto a : cand) {
            int y = 0;
            for (int i = 0; i < 8; i++) {
                y += best[i] == a[i];
            }
            
            if (x == y) ncand.push_back(a);
        }
        
        swap(cand, ncand);
    }
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    dfs(vector<int>(8, -1));
    string s;
    int x;
    while (true) {
        cin >> s;
        if (s == "END") break;
        cin >> x;
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 32ms
memory: 3796kb

input:

GAME 1
4
3
5
6
8
END

output:

RQKBBNRN
RQKNBRNB
RKRNBBQN
RKRBBNNQ
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 1657ms
memory: 3780kb

input:

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

output:

RQKBBNRN
RQKNBRNB
RKRNBBQN
RKRBBNNQ
RKRBBQNN
RQKBBNRN
RKNRBNQB
RKNBBRQN
RKRBBNQN
RQKBBNRN
RQKNBRNB
RKRNBBQN
RKBRNNQB
RKRBBNNQ
RQKBBNRN
RQKNBRNB
RKBRNNQB
RKRNQBBN
RKRBQNBN
RQKBBNRN
NRNBBKQR
RKRBBNNQ
RKRBBQNN
RKRBBNQN
RKRBNQBN
RQKBBNRN
NRNBBKQR
RKRBBNNQ
RKRBNNBQ
RQKBBNRN
NRNBBKQR
RKRBBNNQ
RKRBBNQN
RKR...

result:

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

Test #3:

score: 0
Accepted
time: 1520ms
memory: 3856kb

input:

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

output:

RQKBBNRN
RQKNBRNB
RKRNBBQN
RKRBBNNQ
RKQBBNNR
RQKBBNRN
NRNBBKQR
RKNRBQNB
RKNBBQNR
RQKBBNRN
RQKNBRNB
NRQKBBRN
RKRQBNNB
RKNBBNQR
RQKBBNRN
NRNBBKQR
NRKBQNBR
RKRBBNNQ
RKRBBNQN
RKQBNNBR
RQKBBNRN
NRNBBKQR
QRKBNNBR
RKRNQNBB
RKNBQNBR
RQKBBNRN
NRKBBQNR
RBNKBNQR
RKRBNQBN
RKNBNQBR
RQKBBNRN
NRKBBQNR
RBNKBNQR
RKR...

result:

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

Test #4:

score: 0
Accepted
time: 1621ms
memory: 4008kb

input:

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

output:

RQKBBNRN
NRNBBKQR
NRKBQNBR
RKBQRBNN
QRKRBBNN
RQKBBNRN
NRNBBKQR
RKNRBQNB
RKRBBNNQ
NRKRBBQN
RQKBBNRN
NRKBBQNR
RKBNRBNQ
RKRBBNNQ
NRKRBBNQ
RQKBBNRN
NRNBBKQR
NRKBQNBR
RKRBNNBQ
RKRBBNNQ
QRKRBNNB
RQKBBNRN
NRKBBQNR
RKRBNNBQ
RKRBBQNN
NRKRBQNB
RQKBBNRN
NRNBBKQR
RKNRBQNB
RKRBBNNQ
NRKRBNQB
RQKBBNRN
NRKBBQNR
RNQ...

result:

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

Test #5:

score: 0
Accepted
time: 1642ms
memory: 3752kb

input:

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

output:

RQKBBNRN
NRNBBKQR
RKRBBNNQ
RKRNNBBQ
RKRBBNQN
RQNKRBBN
RQKBBNRN
NRKBBQNR
RKNNRBBQ
RKRBNQBN
RKRBBNNQ
RNQKRBBN
RQKBBNRN
RNBBNKRQ
RBBNKRNQ
RKNRNQBB
RKRBBNNQ
RNNKRBBQ
RQKBBNRN
NRNBBKQR
RKRBBNNQ
RQKBNNBR
RQNKRNBB
RQKBBNRN
NRKBBQNR
RKNNRBBQ
RKNRNBBQ
RKRBNNBQ
RNQKRNBB
RQKBBNRN
RNBBNKRQ
RKNNQRBB
RKNQNBBR
RNN...

result:

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

Test #6:

score: 0
Accepted
time: 1646ms
memory: 3696kb

input:

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

output:

RQKBBNRN
NRKBBQNR
NRBKQNRB
QBBRNKRN
RKRBBNQN
QRBKNBRN
RQKBBNRN
NRKBBQNR
RNQKBBNR
QBRNKNBR
RKRBBNNQ
NRBKQBRN
RQKBBNRN
RNBBNKRQ
NRQNBKRB
RKRNBBNQ
NRBKNBRQ
RQKBBNRN
NRKBBQNR
NRBKQNRB
RKRBNNBQ
QRBKNNRB
RQKBBNRN
NRKBBQNR
RNQKBBNR
QRKNNRBB
RKRBBQNN
NRBKQNRB
RQKBBNRN
RNBBNKRQ
RBBNKRNQ
NRBKNBQR
RKRBBNNQ
NRB...

result:

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

Test #7:

score: 0
Accepted
time: 1637ms
memory: 3804kb

input:

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

output:

RQKBBNRN
NRKBBQNR
NRBKQNRB
RKQRNNBB
RKRBBNNQ
RBBQKRNN
RQKBBNRN
NRKBBQNR
RKNNRBBQ
BBNRKQRN
RKRBBNNQ
RBBNKRQN
RQKBBNRN
RNBBNKRQ
RBBNKRNQ
RQKBBNRN
NRKBBQNR
RKNNRBBQ
RKNRNBBQ
RKRBNNBQ
RBQNKRBN
RQKBBNRN
NRKBBQNR
RKNNRBBQ
RKNRNBBQ
RKRBQNBN
RBNQKRBN
RQKBBNRN
RNBBNKRQ
RKNNQRBB
RKRQBNNB
RKRBBNNQ
RBNNKRBQ
RQK...

result:

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

Test #8:

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

input:

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

output:

RQKBBNRN
NRKBBQNR
RBNKBNQR
RKRBNQBN
RKRBBNNQ
QRNBKNBR
RQKBBNRN
NRKBBQNR
RKBBRNNQ
RKRBNNBQ
NRQBKNBR
RQKBBNRN
RNBBNKRQ
BBRKRNQN
RKQNNRBB
RKRBBQNN
NRNBKQBR
RQKBBNRN
NRQKNRBB
RBNNQKBR
RKRBNQBN
QRNNKBBR
RQKBBNRN
NRQKNRBB
RKQNNBBR
NRQNKBBR
RQKBBNRN
NRQKNRBB
RNQNKRBB
BRKQNBNR
NRNQKBBR
RQKBBNRN
RNBBNKRQ
NBR...

result:

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

Test #9:

score: 0
Accepted
time: 1652ms
memory: 4004kb

input:

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

output:

RQKBBNRN
RNBBNKRQ
BBRKRNQN
QRKNBRNB
RKRBBNNQ
QBBRKNNR
RQKBBNRN
NRQKNRBB
NRBKQBNR
NNBRKRQB
NBBRKQNR
RQKBBNRN
RNBBNKRQ
BBRKRNQN
RBKNBNQR
RKRBBNQN
NBBRKNQR
RQKBBNRN
RNBBNKRQ
NBRNKRBQ
RQKNNBBR
RKRBQNBN
QBNRKNBR
RQKBBNRN
RNBBNKRQ
NBRNKRBQ
RKRNBBNQ
RKNRBBQN
NBQRKNBR
RQKBBNRN
NRQKNRBB
RBNNQKBR
RKRBNQBN
NBN...

result:

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

Test #10:

score: 0
Accepted
time: 1663ms
memory: 4064kb

input:

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

output:

RQKBBNRN
NRQKNRBB
NRBKQBNR
RKRQNBBN
RKRBBNNQ
BBRQNKNR
RQKBBNRN
NRQKNRBB
RBKNRQBN
RKNRBQNB
BBRNQKNR
RQKBBNRN
NRQKNRBB
NRBKQBNR
RKRNBBQN
BBRNNKQR
RQKBBNRN
NRKBBQNR
RBNKBNQR
RBKRNNBQ
RKRBBNNQ
BQRBNKNR
RQKBBNRN
RNBBNKRQ
RBBNKRNQ
NRBKNBQR
RKRBBNNQ
BNRBQKNR
RQKBBNRN
RNBBNKRQ
NRQNBKRB
BNRBKNRQ
BNRBNKQR
RQK...

result:

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

Test #11:

score: 0
Accepted
time: 1641ms
memory: 3784kb

input:

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

output:

RQKBBNRN
RKNRBNQB
RKNBRQBN
RQNBBNKR
RQKBBNRN
RQKNBRNB
NRQKBBRN
RKBRNBNQ
RNQBBNKR
RQKBBNRN
NRNBBKQR
RKNRBQNB
RKRBBNNQ
RNNBBQKR
RQKBBNRN
NRNBBKQR
QRKBNNBR
RKNNBRQB
RQNNBBKR
RQKBBNRN
NRKBBQNR
RNQKBBNR
RKRNBQNB
RNQNBBKR
RQKBBNRN
NRKBBQNR
RNQKBBNR
RKRBBNQN
RNNQBBKR
RQKBBNRN
NRKBBQNR
RBNKBNQR
RQNBNKBR
RKB...

result:

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

Extra Test:

score: 0
Extra Test Passed