QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#647584#7179. Fischer's Chess Guessing Gameno_RED_no_DEADAC ✓200ms4032kbC++202.5kb2024-10-17 14:48:132024-10-17 14:48:17

Judging History

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

  • [2024-10-17 14:48:17]
  • 评测
  • 测评结果:AC
  • 用时:200ms
  • 内存:4032kb
  • [2024-10-17 14:48:13]
  • 提交

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;
}

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: 3788kb

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: 198ms
memory: 3796kb

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: 181ms
memory: 3732kb

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: 191ms
memory: 4032kb

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: 200ms
memory: 3972kb

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: 197ms
memory: 3740kb

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: 184ms
memory: 4004kb

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: 182ms
memory: 3632kb

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: 188ms
memory: 3736kb

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: 143ms
memory: 3828kb

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: 75ms
memory: 3740kb

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