QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#710503#7179. Fischer's Chess Guessing Gameno_RED_no_DEADAC ✓144ms3956kbC++202.9kb2024-11-04 20:09:292024-11-04 20:09:30

Judging History

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

  • [2024-11-04 20:09:30]
  • 评测
  • 测评结果:AC
  • 用时:144ms
  • 内存:3956kb
  • [2024-11-04 20:09:29]
  • 提交

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;

ll pp[N];
vector<string> v;
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;
        v.push_back(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;
}

// NX1: Định lý Phong: càng gần trung tâm x thì càng nhiều trường hợp 
// Lần thử 1: Đỉnh càng lớn thì càng tệ

void doTest(ll testID) {
    backtrack(1, 0, 0, 0, 0, 0); 

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

        vector<string> cv = v; 
        for (int i = 1; ; i ++) {
            assert(i <= 6);
            string chs = "RNNKBBQR";

            if (i != 1) {
                ll mx = 1e18;
                for (auto x: cv) {
                    // Reset
                    for (int j = 0; j <= 8; j ++) pp[j] = 0;

                    // Lập cái đồ thị
                    for (auto y: cv) pp[get(x, y)] ++;
                    
                    // Tính phương sai
                    ll avg = 0, v = 0;
                    for (int j = 0; j <= 8; j ++) avg += pp[j]; avg /= 9;
                    for (int j = 0; j <= 8; j ++) v += (pp[j] - avg) * (pp[j] - avg);

                    // Chọn đồ thị có phương sai bé nhất
                    if (v < mx) mx = v, 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: 1ms
memory: 3588kb

input:

GAME 1
2
3
3
5
8
END

output:

RNNKBBQR
RKBQNBRN
RKQBNNBR
RKRQBNNB
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 144ms
memory: 3656kb

input:

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

output:

RNNKBBQR
RKBQNBRN
RKQBNNBR
RKRQBNNB
RKRBBQNN
RNNKBBQR
BRNQNBKR
RNBKRQNB
RBKRBNQN
RKRBBNQN
RNNKBBQR
RKBQNBRN
RBQKRNBN
RQBBKNNR
RKRBBNNQ
RNNKBBQR
RBBNQKRN
NNBQRKRB
RBKRNQBN
RKRBQNBN
RNNKBBQR
RBBNQKRN
BBRQNKNR
RKBBNRNQ
RKRBNQBN
RNNKBBQR
RBBNQKRN
QRKBBRNN
BRNQKNRB
RKRBNNBQ
RNNKBBQR
BRNQNBKR
RKNBQNBR
NNQ...

result:

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

Test #3:

score: 0
Accepted
time: 115ms
memory: 3648kb

input:

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

output:

RNNKBBQR
BRNQNBKR
RKNNBQRB
RKQRBBNN
RKQBBNNR
RNNKBBQR
RBNKBNRQ
RNBKRBNQ
RKNBBQNR
RNNKBBQR
RBNKBQNR
RNBKQBNR
RKNBBNQR
RNNKBBQR
RKBQNBRN
RKQBNNBR
RNNKBBQR
BRNQNBKR
RKNBQNBR
RNNKBBQR
BRNQNBKR
NQRKNBBR
RKNBNQBR
RNNKBBQR
RBNKBNRQ
NRNQBBKR
RKNNQBBR
RKQNBBNR
RNNKBBQR
RBNKBQNR
RNNBBQKR
RBNNBKQR
RKNQBBNR
RNN...

result:

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

Test #4:

score: 0
Accepted
time: 117ms
memory: 3956kb

input:

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

output:

RNNKBBQR
RKBQNBRN
RBQKRNBN
BRNKNQRB
QRKRBBNN
RNNKBBQR
BRNQNBKR
RKNBQNBR
BNRKRBNQ
NRKRBBQN
RNNKBBQR
RKBQNBRN
QBRKNNBR
NRKBBRQN
NRNBBKRQ
NRKRBBNQ
RNNKBBQR
RBBNQKRN
NNRBKRBQ
BRKRNNQB
QRKRBNNB
RNNKBBQR
RBBNQKRN
NNRBKRBQ
BRQBNNKR
NRKRBQNB
RNNKBBQR
RKBQNBRN
NRQBBKNR
NQRKBRNB
NRKRBNQB
RNNKBBQR
RBBNQKRN
QRK...

result:

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

Test #5:

score: 0
Accepted
time: 101ms
memory: 3588kb

input:

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

output:

RNNKBBQR
RBNKBNRQ
RNBKRBNQ
RNNKRQBB
RQNKRBBN
RNNKBBQR
RBNKBNRQ
NRNQBBKR
RNBBKNQR
RNQKRBBN
RNNKBBQR
RBNKBQNR
RNQNBBKR
RNNKRBBQ
RNNKBBQR
BRNQNBKR
RKNNBQRB
RKQRBBNN
RQNKRNBB
RNNKBBQR
BRNQNBKR
RNBKRQNB
RNBKQNRB
RNQKRNBB
RNNKBBQR
RBNKBNRQ
RNBKRBNQ
RNNKRQBB
RNNKBBQR
RKBQNBRN
RKQBNNBR
RNBNKQRB
RBBKQRNN
RNN...

result:

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

Test #6:

score: 0
Accepted
time: 128ms
memory: 3704kb

input:

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

output:

RNNKBBQR
RKBQNBRN
RKBRQBNN
RBBKNQRN
QRBKNBRN
RNNKBBQR
RKBQNBRN
RKBNNRQB
BRQKNBRN
NRBKQBRN
RNNKBBQR
RKBQNBRN
RKBNNRQB
RNBBQKRN
RQKRNBBN
NRBKNBRQ
RNNKBBQR
RBBNQKRN
BBRQNKNR
NRBKNQRB
QRBKNNRB
RNNKBBQR
RBBNQKRN
NNBQRKRB
NRBQKBRN
NRBKQNRB
RNNKBBQR
RBBNQKRN
BBRQNKNR
NRBKNQRB
RNNKBBQR
RBNKBNRQ
RNKNBBRQ
RBN...

result:

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

Test #7:

score: 0
Accepted
time: 121ms
memory: 3716kb

input:

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

output:

RNNKBBQR
RBBNQKRN
BNRNQKRB
RBBQKRNN
RNNKBBQR
RKBQNBRN
RKQBNNBR
RNBNKQRB
RBBNKRQN
RNNKBBQR
RBBNQKRN
BNRNQKRB
RBBNKRNQ
RNNKBBQR
RBBNQKRN
BNRNQKRB
RBBNKRNQ
RBQNKRBN
RNNKBBQR
RKBQNBRN
RKQBNNBR
RBQNBKRN
RBNQKRBN
RNNKBBQR
RKBQNBRN
QBRKNNBR
BRNBNQKR
NRBKRNQB
RBNNKRBQ
RNNKBBQR
RBBNQKRN
NNBQRKRB
BBRKNQRN
RBK...

result:

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

Test #8:

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

input:

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

output:

RNNKBBQR
RKBQNBRN
NRQBBKNR
NQRKBRNB
BNQBRNKR
QRNBKNBR
RNNKBBQR
RBBNQKRN
NNRBKRBQ
NQRKNRBB
NRKBBRNQ
NRQBKNBR
RNNKBBQR
RKBQNBRN
NRQBBKNR
BNRBQKNR
NRNBKQBR
RNNKBBQR
BRNQNBKR
BNNBRQKR
BRNKNRQB
RBNQNKBR
QRNNKBBR
RNNKBBQR
RKBQNBRN
QBRKNNBR
BRNBNQKR
NRKNQBBR
NRQNKBBR
RNNKBBQR
BRNQNBKR
BNQRNBKR
NRNQKBBR
RNN...

result:

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

Test #9:

score: 0
Accepted
time: 127ms
memory: 3708kb

input:

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

output:

RNNKBBQR
RBBNQKRN
BBRQNKNR
QBBRKNNR
RNNKBBQR
RBBNQKRN
BBRQNKNR
QBBRKNNR
NBBRKQNR
RNNKBBQR
RKBQNBRN
QBRKNNBR
BNRBNQKR
NBNQRKBR
NBBRKNQR
RNNKBBQR
RKBQNBRN
NRQBBKNR
BNRKRQNB
QBNRKNBR
RNNKBBQR
RBBNQKRN
QRKBBRNN
NBQRKNBR
RNNKBBQR
RKBQNBRN
NRQBBKNR
NRNKRQBB
NBNRKQBR
RNNKBBQR
BRNQNBKR
RKNBQNBR
RNBQKBRN
BNR...

result:

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

Test #10:

score: 0
Accepted
time: 140ms
memory: 3708kb

input:

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

output:

RNNKBBQR
RBBNQKRN
BBRQNKNR
RNNKBBQR
RBBNQKRN
BNRNQKRB
NNBRQKRB
BBRNQKNR
RNNKBBQR
RKBQNBRN
QBRKNNBR
QRNBNKBR
BBRNNKQR
RNNKBBQR
RBBNQKRN
QRKBBRNN
NRBBNQKR
BQRBNKNR
RNNKBBQR
RKBQNBRN
NRQBBKNR
BNRBQKNR
RNNKBBQR
BRNQNBKR
NQRKNBBR
RKNBNQBR
NQNBBRKR
BNRBNKQR
RNNKBBQR
RKBQNBRN
NRQBBKNR
BNRBQKNR
BRNBKQNR
QBR...

result:

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

Test #11:

score: 0
Accepted
time: 130ms
memory: 3708kb

input:

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

output:

RNNKBBQR
RBNKBNRQ
RNKNBBRQ
RBNQBKNR
RQNBBNKR
RNNKBBQR
RBNKBNRQ
RNBKRBNQ
RKNBBQNR
RNQBBNKR
RNNKBBQR
RBNKBQNR
RNNBBQKR
RNNKBBQR
RBNKBQNR
RNBKQBNR
RQNNBBKR
RNNKBBQR
RBNKBQNR
RNQNBBKR
RNNKBBQR
RNKNBBQR
RNNQBBKR
RNNKBBQR
RBBNQKRN
NNRBKRBQ
BRQBNNKR
RNNKBBQR
RKBQNBRN
NRQBBKNR
NQRKBRNB
BNQBRNKR
BRNBQNKR
RNN...

result:

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

Extra Test:

score: 0
Extra Test Passed