QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#647528#7179. Fischer's Chess Guessing Gameno_RED_no_DEADTL 220ms4048kbC++203.0kb2024-10-17 14:35:432024-10-17 14:35:43

Judging History

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

  • [2024-10-17 14:35:43]
  • 评测
  • 测评结果:TL
  • 用时:220ms
  • 内存:4048kb
  • [2024-10-17 14:35:43]
  • 提交

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 ++) {
            const string fuck[] = {
                "RBNKQRBN", 
                "BQRKNBNR", 
                "RKRBBQNN", 
                "NNRKRBBQ",
                "NNBBRKQR",
                "RKQBBNNR",
                "NQNRBKRB",
                "NQNRBKRB"
            };

            string chs; ld cur = 1e18;
            if (i == 1) chs = fuck[rand(0, 7)];
            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: 5ms
memory: 3948kb

input:

GAME 1
1
2
3
1
3
8
END

output:

NNBBRKQR
RKNNQBBR
RNQKBBRN
BNRNKBRQ
RBKNBRQN
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 181ms
memory: 3864kb

input:

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

output:

NNBBRKQR
RKNNQBBR
RNQKBBRN
BNRNKBRQ
RBKNBRQN
RKRBBQNN
NNRKRBBQ
NRBBNQKR
BQNRKBNR
QBBNRKRN
RKRBBNQN
RBNKQRBN
RQBNKNRB
RNKRBQNB
RKBRNBNQ
RKQNBBNR
RKRBBNNQ
RKRBBQNN
RKRBQNBN
NQNRBKRB
BNRNQBKR
BRQBKRNN
RKBQRBNN
RKRBNQBN
NQNRBKRB
BNRNQBKR
BRQBKRNN
RBBKNQNR
QBRKRNBN
RKRBNNBQ
NNRKRBBQ
NRNQBBKR
RNBNQBKR
RQN...

result:

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

Test #3:

score: 0
Accepted
time: 200ms
memory: 3768kb

input:

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

output:

RKQBBNNR
NQNRBKRB
NRNQKBBR
RBNNBQKR
RKNBBQNR
NNBBRKQR
RKNBBNQR
BQRKNBNR
RNBBNQKR
RKBRNQNB
RBBNNKQR
RKQBNNBR
NQNRBKRB
BRNQKBNR
QRBBKNRN
RKBRQBNN
BNRKQBRN
RKNBQNBR
NQNRBKRB
BRNQKBNR
QRBBKNRN
RKBQNRNB
RBBNQKNR
RKNBNQBR
RBNKQRBN
RQBNKNRB
RNKRBQNB
RKBRNBNQ
RKQNBBNR
NQNRBKRB
NRNQKBBR
NRQNKRBB
RKNQBBNR
RKQ...

result:

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

Test #4:

score: 0
Accepted
time: 197ms
memory: 4044kb

input:

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

output:

NQNRBKRB
NRNQKBBR
RBNNBQKR
BRNKRNQB
NRKBBRNQ
QRKRBBNN
RKRBBQNN
NRNBBKQR
NQRBNKBR
QRNKBBNR
NRKRBBQN
NNBBRKQR
RKNNQBBR
BNRKNBRQ
BRNBKQRN
NRKRBBNQ
NNRKRBBQ
BRNBNKQR
RQKBBNRN
RBKNBQNR
QRKRBNNB
RBNKQRBN
BRKNNQRB
NRQNBKRB
BNQRNKRB
NRKRBQNB
NNRKRBBQ
NRBBNQKR
QBBNRKNR
NRKQBNRB
NRKRBNQB
NNRKRBBQ
NRNQBBKR
NRB...

result:

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

Test #5:

score: 0
Accepted
time: 204ms
memory: 4048kb

input:

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

output:

RKQBBNNR
NRKQNBBR
NRBKQNRB
NBQRKRBN
QBBNNRKR
RQNKRBBN
RKRBBQNN
NRNBBKQR
BBRNKRNQ
RKBQNNRB
RNKRQBBN
RNQKRBBN
NQNRBKRB
BRNQKBNR
QRBBKNRN
RKNNRBBQ
RNNKRBBQ
RKQBBNNR
RBBNNQKR
QRBKRNNB
QRBBKRNN
RQNKRNBB
BQRKNBNR
RKNBBNQR
RNKQBRNB
RNQKRNBB
RKQBBNNR
NRKQNBBR
RBBNNKRQ
BRNKQNRB
BQRKNRNB
RNNKRQBB
RBNKQRBN
RBN...

result:

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

Test #6:

score: 0
Accepted
time: 192ms
memory: 3968kb

input:

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

output:

RKRBBQNN
RBQKNNBR
NRBBNKQR
QBBNRKNR
NRQNBBKR
QRBKNBRN
NQNRBKRB
NRNQKBBR
NRBBQKNR
NRBBKQRN
NRBKQBRN
NQNRBKRB
NRNQKBBR
NRBBQKNR
NRBNKRQB
NQBNRBKR
NRBKNBRQ
NQNRBKRB
NRNQKBBR
BRKNNQRB
RNKRNQBB
QRBKNNRB
NNRKRBBQ
NRNQBBKR
NRBKNQRB
NRBKNRQB
NRBKQNRB
NQNRBKRB
RQNKBBNR
NBNRKRBQ
NRBKNQRB
RBNKQRBN
QRNKNBBR
NRN...

result:

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

Test #7:

score: 0
Accepted
time: 220ms
memory: 3744kb

input:

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

output:

NNBBRKQR
RKNNQBBR
BNRKNBRQ
NBQRKRBN
RBBQKRNN
RKRBBQNN
NRNBBKQR
BQRKNBNR
RKNQRNBB
RBBNKRQN
NNRKRBBQ
NRBBNQKR
BQNRKBNR
BRNKQNRB
QBRNBKNR
RBBNKRNQ
NNRKRBBQ
NRBBNQKR
BBRNKRQN
BBRNQKRN
BQRNKRNB
RBQNKRBN
RBNKQRBN
RBNKNRBQ
RBNKBRQN
RBNKRQBN
RBNQKRBN
RKQBBNNR
NRKQNBBR
RBBNNKRQ
BBRKNNRQ
NNBBRKRQ
RBNNKRBQ
RKQ...

result:

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

Test #8:

score: 0
Accepted
time: 195ms
memory: 4044kb

input:

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

output:

BQRKNBNR
RKNBBNQR
RNQBKNBR
QRNBKNBR
RKRBBQNN
RBQKNNBR
QNRKNBBR
RBBNNKQR
NRQBKNBR
BQRKNBNR
RKNBBNQR
QBNRKNBR
QBNNBRKR
NRNBKQBR
RKQBBNNR
NRKQNBBR
NRBNQBKR
NNRKQBBR
QRNNKBBR
RBNKQRBN
RQBNKNRB
RNKRBQNB
BQNBRNKR
BBRNNKRQ
NRQNKBBR
NNBBRKQR
NRNQBBKR
NBNQBRKR
NRNQKBBR
NQNRBKRB
BNRNQBKR
BRQBKNNR
RBBNKQNR
BBR...

result:

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

Test #9:

score: 0
Accepted
time: 186ms
memory: 3800kb

input:

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

output:

BQRKNBNR
RNBBNQKR
BRNBKNQR
QRNNBBKR
NQNBRKBR
QBBRKNNR
BQRKNBNR
RNBBNQKR
RKBQNRNB
RBQNNKBR
NBBRKQNR
RBNKQRBN
RQBNKNRB
RKBRNQNB
BQRKRNNB
NBBRKNQR
RKQBBNNR
RBBNNQKR
NRBQKBNR
BBNRKNQR
QBNRKNBR
BQRKNBNR
RKNBBNQR
RNKQBRNB
NBBNRKQR
NBNRKQBR
NBQRKNBR
NNBBRKQR
NRNQBBKR
NRKNRBBQ
QRNBKNBR
NBNRKQBR
NQNRBKRB
BRN...

result:

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

Test #10:

score: -100
Time Limit Exceeded

input:

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

output:

NNBBRKQR
NRNQBBKR
NQRKRBBN
RKNBBRQN
BBQNRNKR
BBRQNKNR
RKQBBNNR
RBBNNQKR
RBBQKNRN
NBRNBKQR
BBRNQKNR
BQRKNBNR
RQBNKBNR
BRNQNBKR
BBQRNKNR
BBRNNKQR
NNBBRKQR
RKNBBNQR
RNBQNBKR
BQRBNKNR
NNRKRBBQ
NRNQBBKR
RBQKNNBR
BNRQKNRB
BNRBQKNR
NNBBRKQR
BNRBNKQR
RKRBBQNN
RKBNNQRB
RNQKBBNR
NQRKBBRN
QBRNBKNR
NNRKRBBQ
NRN...

result: