QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#647501#7179. Fischer's Chess Guessing Gameno_RED_no_DEADTL 190ms3872kbC++202.8kb2024-10-17 14:30:092024-10-17 14:30:10

Judging History

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

  • [2024-10-17 14:30:10]
  • 评测
  • 测评结果:TL
  • 用时:190ms
  • 内存:3872kb
  • [2024-10-17 14:30:09]
  • 提交

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[] = {"NNRKRBBQ", "RBNKQRBN", "BQRKNBNR", "NRNBBQKR"};

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

input:

GAME 1
2
3
6
4
8
END

output:

RBNKQRBN
QRNBBKRN
RKNBBQNR
RKNBBNQR
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 185ms
memory: 3872kb

input:

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

output:

BQRKNBNR
RNBBNQKR
RKBQNRNB
RQKBNRBN
RBNQNKBR
RKRBBQNN
NRNBBQKR
RBQNBKNR
RNBQNBKR
QRKNBBRN
RKRBBNQN
BQRKNBNR
RNBBNQKR
BRNBKNQR
QBRNBNKR
QBNRNKBR
RKRBBNNQ
NRNBBQKR
RKQNNBBR
BQRKNBNR
RKRNBNQB
RBBNKNQR
RKRBQNBN
RBNKQRBN
QRNKNBBR
RBQKBNNR
RQKNNRBB
RKRBNQBN
NNRKRBBQ
NRNQKBBR
RNKBNRBQ
RKRBNNBQ
NRNBBQKR
RKQ...

result:

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

Test #3:

score: 0
Accepted
time: 189ms
memory: 3796kb

input:

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

output:

RBNKQRBN
RQBNKNRB
RNKRBQNB
RKBRNBNQ
NBBRKQNR
RKQBBNNR
NNRKRBBQ
BRNBNKQR
QBBRNKNR
BBNRKRQN
QRNNBKRB
RKNBBQNR
NNRKRBBQ
BRNBNKQR
BRQNNKRB
RKNBBNQR
NRNBBQKR
RBQNBKNR
BBQRNNKR
NBBRNKQR
BRQKNBNR
RKQBNNBR
BQRKNBNR
RKNBBNQR
RNKBBNQR
RKNBQNBR
RBNKQRBN
QRNKNBBR
NRQKNRBB
BRNKRBQN
RKNBNQBR
NNRKRBBQ
NRBBNQKR
BQN...

result:

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

Test #4:

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

input:

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

output:

RBNKQRBN
RQBNKNRB
BNNBRQKR
NRKRBBQN
QRKRBBNN
NNRKRBBQ
NRNQBBKR
RNBQNBKR
NRNBKQBR
NRKRBBQN
NRNBBQKR
RNBBQNKR
NRKQBRNB
NRKQBBRN
NRKRBBNQ
NRNBBQKR
RBQNBKNR
RNBQNBKR
NBRKBRQN
QRKNBNRB
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: 140ms
memory: 3764kb

input:

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

output:

NNRKRBBQ
BRNKRBNQ
RKNNRBBQ
RBNKRNBQ
RQNKRBBN
NRNBBQKR
BNRKQRNB
RKBQRNNB
RQKNNRBB
QNBRNKRB
RNQKRBBN
BQRKNBNR
RNBBNQKR
BRNBKNQR
RKNRNBBQ
RBNKNRBQ
RNNKRBBQ
RBNKQRBN
RNKNQRBB
RBBNKRQN
QRNKNRBB
RQNKRNBB
BQRKNBNR
RKNBBNQR
RNKQBRNB
RNQKRNBB
NNRKRBBQ
BRNKRBNQ
NRQKNBBR
RNNKRQBB
RBNKQRBN
RBNKNRBQ
NBRKQRBN
RBB...

result:

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

Test #6:

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

input:

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

output:

NRNBBQKR
RKQNNBBR
RQKNBNRB
NBRNKRBQ
BRKRNBQN
QRBKNBRN
BQRKNBNR
RNBBNQKR
BNRQKNRB
NRBKQRNB
NRBKQBRN
RBNKQRBN
RQBNKNRB
RNKRBQNB
BQNBRNKR
NRBKNBRQ
RBNKQRBN
RQBNKNRB
BQRNKBRN
QRBKNNRB
NRNBBQKR
RBQNBKNR
BRNKRBQN
NRBKQNRB
NRNBBQKR
RNBBQNKR
NRKBNRBQ
NRBKNQRB
BQRKNBNR
RNBBNQKR
BRQNKRNB
NRNKBBRQ
NRNKRBBQ
QRN...

result:

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

Test #7:

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

input:

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

output:

RBNKQRBN
RNKNQRBB
NBRKNRBQ
QRNBKRBN
RBBQKRNN
NNRKRBBQ
BRNBNKQR
RQKBBNRN
RBBQKNNR
RBBNKRQN
BQRKNBNR
RKNBBNQR
RBBQNKRN
BNQBRKRN
RBBNKRNQ
NNRKRBBQ
NRBBNQKR
BBRNKRQN
BBRNQKRN
BQRNKRNB
RBQNKRBN
RBNKQRBN
RBNKNRBQ
RBNKBRQN
RBNKRQBN
RBNQKRBN
RBNKQRBN
RBBKNRQN
RBNKRNBQ
RBNNKRBQ
NRNBBQKR
RKQNNBBR
QNRBKRBN
NBR...

result:

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

Test #8:

score: 0
Accepted
time: 190ms
memory: 3796kb

input:

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

output:

NNRKRBBQ
NRBBNQKR
BQNBRNKR
RQNBNKBR
QRNBKNBR
RBNKQRBN
RQBNKNRB
RNKRBQNB
BQNBRNKR
BRNNKBQR
NRQBKNBR
NNRKRBBQ
NRNQBBKR
RNBQNBKR
NRNBKQBR
RBNKQRBN
QRNBBKRN
RKNBBQNR
BRQBKRNN
BRNKNQRB
QRNNKBBR
RBNKQRBN
RQBNKNRB
RNKRBQNB
BQNBRNKR
BBRNNKRQ
NRQNKBBR
NRNBBQKR
NRKBRQBN
NRNQKBBR
NNRKRBBQ
NRBBNQKR
BBRNKRQN
BBR...

result:

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

Test #9:

score: 0
Accepted
time: 171ms
memory: 3792kb

input:

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

output:

BQRKNBNR
RNBBNQKR
BRNBKNQR
QRNNBBKR
NQNBRKBR
QBBRKNNR
BQRKNBNR
RNBBNQKR
RKBQNRNB
RBQNNKBR
NBBRKQNR
NRNBBQKR
RBQNBKNR
RNBQNBKR
RKNRBBQN
NBBRKNQR
BQRKNBNR
RKNBBNQR
QBNRKNBR
NNRKRBBQ
NRNQBBKR
NRBKNQRB
RNBNKBQR
NBQRKNBR
RBNKQRBN
QRNKNBBR
RBKNNQBR
NBNRKQBR
NRNBBQKR
RKQNNBBR
RQKNBNRB
NNRKRBBQ
NBQRKRBN
QNB...

result:

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

Test #10:

score: 0
Accepted
time: 177ms
memory: 3796kb

input:

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

output:

NNRKRBBQ
NRBBNQKR
QBBNRKNR
QBNRNKBR
BBRNNKQR
BBRQNKNR
RBNKQRBN
QRNBBKRN
RBKNBQNR
RNKQBRNB
BBNRKQNR
BBRNQKNR
BQRKNBNR
RQBNKBNR
BRNQNBKR
BBQRNKNR
BBRNNKQR
BQRKNBNR
BNRKNBQR
BQRBNKNR
BQRKNBNR
RQBNKBNR
BRNQNBKR
BQRNNKRB
BNRBQKNR
BQRKNBNR
RQBNKBNR
BNRKRQNB
BNRBNKQR
RBNKQRBN
RQBNKNRB
NRKBBQRN
BNRBQNKR
BRN...

result:

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

Test #11:

score: -100
Time Limit Exceeded

input:

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

output:

NRNBBQKR
RQNBBNKR
NRNBBQKR
NRKBRQBN
NBRQBNKR
NBNRBKQR
RNQBBNKR
RBNKQRBN
QRNBBKRN
RKNBBQNR
RKNBBNQR
RNNBBQKR
BQRKNBNR
RQNNBBKR
BQRKNBNR
RNBBNQKR
RKBRNQNB
NNBQRBKR
RNQNBBKR
NNRKRBBQ
NRNQBBKR
NQNRBBKR
NRQNBBKR
RNNQBBKR
NRNBBQKR
NRKBRQBN
BQNBRNKR
BRNBKNQR
BRQBNNKR
RBNKQRBN
QRNBBKRN
RKNBBQNR
QBNRBNKR
BRN...

result: