QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#647563#7179. Fischer's Chess Guessing Gameno_RED_no_DEADAC ✓191ms4056kbC++202.8kb2024-10-17 14:44:322024-10-17 14:44:33

Judging History

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

  • [2024-10-17 14:44:33]
  • 评测
  • 测评结果:AC
  • 用时:191ms
  • 内存:4056kb
  • [2024-10-17 14:44:32]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const ll N = 1e6 + 1;
const ll M = 1e9 + 7;
const ll B = 8;

vector<string> v;
set<string> s;
string cur;

void backtrack(ll pos, ll r, ll n, ll b, ll k, ll q) {
    if (pos > B) {
        ll r1 = 1e18, r2 = -1e18, b1 = 1e18, b2 = -1e18, k1 = -1e18;
        for (ll i = 0; i < cur.size(); i ++) {
            if (cur[i] == 'R') r1 = min(r1, i), r2 = max(r2, i);
            if (cur[i] == 'B') b1 = min(b1, i), b2 = max(b2, i);
            if (cur[i] == 'K') k1 = max(k1, i);
        }
        if (b1 % 2 == b2 % 2) return;
        if (r1 > k1 || r2 < k1) return;
        s.insert(cur);
        return;
    }
    if (r < 2) cur += 'R', backtrack(pos + 1, r + 1, n, b, k, q), cur.pop_back();
    if (n < 2) cur += 'N', backtrack(pos + 1, r, n + 1, b, k, q), cur.pop_back();
    if (b < 2) cur += 'B', backtrack(pos + 1, r, n, b + 1, k, q), cur.pop_back();
    if (k < 1) cur += 'K', backtrack(pos + 1, r, n, b, k + 1, q), cur.pop_back();
    if (q < 1) cur += 'Q', backtrack(pos + 1, r, n, b, k, q + 1), cur.pop_back();
}

ll get(string &a, string &b) {
    ll res = 0; 
    for (int i = 0; i < a.size(); i ++)
        if (a[i] == b[i]) res ++;
    return res;
}

mt19937_64 rng(static_cast<ll>(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count()));

ll rand(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

void doTest(ll testID) {
    backtrack(1, 0, 0, 0, 0, 0);
    for (auto x: s) v.push_back(x);

    while (true) {
        string s; ll num; cin >> s; if (s == "END") return; cin >> num;

        vector<string> cv = v; 
        for (int i = 1;; i ++) {
            string chs; ld cur = 1e18;
            if (i == 1) chs = "BBNNRQKR";
            else {
                for (auto x: cv) {
                    map<ll, ll> pp; for (auto y: cv) pp[get(x, y)] ++;
                    ld avg = 0, j = 0; for (auto [x, y]: pp) avg += y, j ++; avg /= pp.size();
                    ld tmp = 0; for (auto [x, y]: pp) tmp += (ld)(y - avg) * (y - avg) / pp.size();
                    if (tmp < cur) cur = tmp, chs = x;
                }
            }
            cout << chs << endl;
            
            ll req; 
            cin >> req; 
            if (req == 8) break;
            
            vector<string> nv;
            for (auto x: cv)
                if (get(x, chs) == req) 
                    nv.push_back(x);
            cv = nv;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int test = 1; 
    // cin >> test;
    for (int _ = 1; _ <= test; _ ++) doTest(_);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 3896kb

input:

GAME 1
1
3
5
4
8
END

output:

BBNNRQKR
RKQNBNRB
RKNBBRNQ
RKBBRNNQ
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 187ms
memory: 3760kb

input:

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

output:

BBNNRQKR
RKQNBNRB
RKNBBRNQ
RKBBRNNQ
RKRBBQNN
BBNNRQKR
RKBQNNRB
NRBBNKRQ
RNBKQRNB
RKQRNBBN
RKRBBNQN
BBNNRQKR
RKBQNNRB
NRBBNKRQ
RNBKQBRN
RKRBBNNQ
BBNNRQKR
RKBQNNRB
NRBBNKRQ
RNBKQRNB
RKRBQNBN
BBNNRQKR
RKQNBNRB
RQKBNNBR
NRQBKNBR
RBKRQNBN
RKRBNQBN
BBNNRQKR
RKBQNNRB
RKRQNBBN
RKBRNBQN
RKRBNNBQ
BBNNRQKR
RKB...

result:

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

Test #3:

score: 0
Accepted
time: 183ms
memory: 3816kb

input:

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

output:

BBNNRQKR
RKQNBNRB
RKNBBNRQ
RKNRBNQB
RKQBBNNR
BBNNRQKR
NBRQBNKR
BNRBKQNR
RNBBNQKR
RKNBBQNR
BBNNRQKR
RKNNBBRQ
RKBNNBQR
RKNBBNQR
BBNNRQKR
RKQNBNRB
RQKNBBRN
BNQRKNRB
RKBQRNNB
RKQBNNBR
BBNNRQKR
RKNNBBRQ
RQKNNBBR
RBNKNRBQ
RBKNBRQN
RKNBQNBR
BBNNRQKR
NBRQBNKR
BRNKNBQR
RKNBNQBR
BBNNRQKR
RKNNBBRQ
RBNKBNRQ
RKB...

result:

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

Test #4:

score: 0
Accepted
time: 182ms
memory: 3824kb

input:

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

output:

BBNNRQKR
RKBQNNRB
NRKRQBBN
NRKRBBNQ
QRKRBBNN
BBNNRQKR
RKBQNNRB
NRKRQBBN
NRKBQRBN
NRKRBBQN
BBNNRQKR
RKBQNNRB
NRKRQBBN
NRKRBBNQ
BBNNRQKR
RKBQNNRB
NRBKQRNB
RNBBKRNQ
QRKRBNNB
BBNNRQKR
RKQNBNRB
RQKBNNBR
BRQKNRNB
NRBKRNQB
NRKRBQNB
BBNNRQKR
RKBQNNRB
NRBKQRNB
RNBBKRNQ
NRKRBNQB
BBNNRQKR
RKBQNNRB
NNRKBBRQ
RQK...

result:

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

Test #5:

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

input:

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

output:

BBNNRQKR
RKNNBBRQ
RQKNNBBR
RQNKRBBN
BBNNRQKR
RKQNBNRB
RQKBNNBR
NRKBBQRN
RKNRQBBN
RNQKRBBN
BBNNRQKR
RKNNBBRQ
RKBNNBQR
BNRNKBRQ
RNKNBQRB
RNNKRBBQ
BBNNRQKR
RKNNBBRQ
NRNQKBBR
RBNKQRBN
RQNKRNBB
BBNNRQKR
RKQNBNRB
RQKNBBRN
BNQRKNRB
RNQKRNBB
BBNNRQKR
NBRQBNKR
BRKNRBNQ
BNNRKQRB
RNNKRQBB
BBNNRQKR
RKQNBNRB
QNR...

result:

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

Test #6:

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

input:

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

output:

BBNNRQKR
RKBQNNRB
NRBBNKRQ
NRBKNRQB
QRBKNBRN
BBNNRQKR
RKBQNNRB
NRBKQRNB
NQBRKRNB
NRBKQBRN
BBNNRQKR
RKBQNNRB
NRBBNKRQ
NRBBKNRQ
NRBKNBRQ
BBNNRQKR
RKBQNNRB
RKRQBNNB
NRBQNKRB
QRBKNNRB
BBNNRQKR
RKBQNNRB
RKRQNBBN
NQBRKNRB
NRBKQNRB
BBNNRQKR
RKQNBNRB
RQKBNNBR
BRQKNRNB
NRBKNQRB
BBNNRQKR
RKQNBNRB
RQKBNNBR
QRB...

result:

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

Test #7:

score: 0
Accepted
time: 178ms
memory: 4056kb

input:

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

output:

BBNNRQKR
RKQNBNRB
QNRKBBNR
QBBRNKRN
BRKQNBRN
RBBQKRNN
BBNNRQKR
RKNNBBRQ
NRNQKBBR
NQBNRKRB
NBRKBQRN
RBBNKRQN
BBNNRQKR
RKNNBBRQ
RQKNNBBR
RKBNRNQB
RBBNKRNQ
BBNNRQKR
RKNNBBRQ
NRNQKBBR
RBNKQRBN
RBQNKRBN
BBNNRQKR
RKNNBBRQ
NRNQKBBR
QNRNKBBR
NBNRKRBQ
RBNQKRBN
BBNNRQKR
NBRQBNKR
BRNKNBQR
BNRNKQRB
RBNNKRBQ
BBN...

result:

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

Test #8:

score: 0
Accepted
time: 170ms
memory: 3984kb

input:

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

output:

BBNNRQKR
RKNNBBRQ
BRNBKRQN
BNRNKRQB
BRKBNQRN
QRNBKNBR
BBNNRQKR
RKQNBNRB
RQKBNNBR
NRQBKNBR
BBNNRQKR
NBRQBNKR
BNRBKQNR
RNBBNQKR
NRNBKQBR
BBNNRQKR
NBRQBNKR
BRNKNBQR
BRKBNQNR
QRNNKBBR
BBNNRQKR
RKNNBBRQ
NRNQKBBR
NQNRKBBR
NRNKQBBR
NRQNKBBR
BBNNRQKR
RKNNBBRQ
NRNQKBBR
BBNNRQKR
RKNNBBRQ
NNRBKQBR
BRKBQNNR
BBR...

result:

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

Test #9:

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

input:

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

output:

BBNNRQKR
RKNNBBRQ
NNRBKQBR
BRKBQNNR
NBBRQKNR
QBBRKNNR
BBNNRQKR
NBRQBNKR
RBQNKNBR
NBBRKQNR
BBNNRQKR
RKNNBBRQ
NNRBKQBR
NQBBNRKR
NBBRKNQR
BBNNRQKR
NBRQBNKR
RBQNKNBR
BBQRKNNR
QBNRKNBR
BBNNRQKR
RKNNBBRQ
NNRBKQBR
BNRBNKQR
NBQRKNBR
BBNNRQKR
BRNBKQNR
BQNBNRKR
BBNRKQRN
NBNRKQBR
BBNNRQKR
RKQNBNRB
NNRKQBBR
NBR...

result:

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

Test #10:

score: 0
Accepted
time: 132ms
memory: 3820kb

input:

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

output:

BBNNRQKR
NBRQBNKR
RQNBBNKR
NBBQRKNR
BBRQNKNR
BBNNRQKR
BRNBKQNR
NBRNKQBR
BBRNQKNR
BBNNRQKR
BRNBKQNR
BBRQNNKR
BBRNNKQR
BBNNRQKR
RKNNBBRQ
NNRBKQBR
NQBBNRKR
BQRBNKNR
BBNNRQKR
RKNNBBRQ
NNRBKQBR
BNRBNKQR
BNRBQKNR
BBNNRQKR
RKNNBBRQ
NNRBKQBR
BNRBNKQR
BBNNRQKR
NBRQBNKR
RQNBBNKR
QBRNBKNR
BBNNRQKR
RKNNBBRQ
BRN...

result:

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

Test #11:

score: 0
Accepted
time: 66ms
memory: 3772kb

input:

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

output:

BBNNRQKR
NBRQBNKR
RQNBBNKR
BBNNRQKR
RKNNBBRQ
NRNQKBBR
NQBNRKRB
RBQKBNNR
RNQBBNKR
BBNNRQKR
BRNBKQNR
BQNBNRKR
BNNBRKQR
RNNBBQKR
BBNNRQKR
BRNBKQNR
BBRQNNKR
RBNNBKQR
RQNNBBKR
BBNNRQKR
NBRQBNKR
RBQNKNBR
QBRNNKBR
RNQNBBKR
BBNNRQKR
NBRQBNKR
RQNBBNKR
BQRBNNKR
RBNKBNQR
RNNQBBKR
BBNNRQKR
NBRQBNKR
RBQNKNBR
NBB...

result:

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

Extra Test:

score: 0
Extra Test Passed