QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#710490#7179. Fischer's Chess Guessing Gameno_RED_no_DEADAC ✓153ms3952kbC++202.9kb2024-11-04 20:04:452024-11-04 20:04:45

Judging History

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

  • [2024-11-04 20:04:45]
  • 评测
  • 测评结果:AC
  • 用时:153ms
  • 内存:3952kb
  • [2024-11-04 20:04:45]
  • 提交

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 = "RNKBRQBN";

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

input:

GAME 1
4
2
3
3
8
END

output:

RNKBRQBN
RBKNQRBN
BRKBNQRN
RNKBBNRQ
RKRBBQNN

result:

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

Test #2:

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

input:

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

output:

RNKBRQBN
RBKNQRBN
BRKBNQRN
RNKBBNRQ
RKRBBQNN
RNKBRQBN
RNBBQKNR
RNKNBRQB
RQKNNBBR
RKRBBNQN
RNKBRQBN
RKBNQBRN
RKQBBNNR
RKRBBNNQ
RNKBRQBN
RBKNQRBN
RQNBKRBN
RQKRNBBN
RKRBQNBN
RNKBRQBN
RNKRNQBB
RKRBNQBN
RNKBRQBN
RNBBQKNR
RNKNBRQB
RKNRQBBN
RBNKNQBR
RKRBNNBQ
RNKBRQBN
RKBNQBRN
RKBBQNNR
RKRQBBNN
RNKBRQBN
RKB...

result:

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

Test #3:

score: 0
Accepted
time: 68ms
memory: 3676kb

input:

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

output:

RNKBRQBN
RKBNQBRN
RKQBBNNR
RNKBRQBN
RNBBQKNR
RNBKQBRN
RKNBBQNR
RNKBRQBN
RKBNQBRN
RKQBBNNR
RKRBBNNQ
RKNBBNQR
RNKBRQBN
RNBBQKNR
RNBQKBRN
NNRBBQKR
RKQBNNBR
RNKBRQBN
RNBBQKNR
RNBKQBRN
RNQBBNKR
RKNBQNBR
RNKBRQBN
RBKNQRBN
BRKBNQRN
RNKBBNRQ
RKNBNQBR
RNKBRQBN
RQBNNBKR
BNRQNBKR
RKNNBBQR
RKQNBBNR
RNKBRQBN
RQB...

result:

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

Test #4:

score: 0
Accepted
time: 119ms
memory: 3952kb

input:

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

output:

RNKBRQBN
RKBNQBRN
RKQBBNNR
QRNBBKRN
RNNQBKRB
QRKRBBNN
RNKBRQBN
RKBNQBRN
RKQBBNNR
NRKRBBQN
RNKBRQBN
RQBNNBKR
BBRNQKRN
QRNKNRBB
RKQRBNNB
NRKRBBNQ
RNKBRQBN
RQBNNBKR
BBRKQRNN
NNRQBKRB
QRKRBNNB
RNKBRQBN
RKBNQBRN
QNNBBRKR
NRKQNRBB
NRKRBQNB
RNKBRQBN
RQBNNBKR
BBRKQRNN
NRKRBNQB
RNKBRQBN
RNBBQKNR
NQRKRBBN
BRK...

result:

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

Test #5:

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

input:

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

output:

RNKBRQBN
RBKNQRBN
RNKQBBRN
RNBBKRQN
RQNKRBBN
RNKBRQBN
RNKRNQBB
RNBBKQRN
RNQKRBBN
RNKBRQBN
RBKNQRBN
BRKBNQRN
RNNKRBBQ
RNKBRQBN
RNBBQKNR
NRKBBRQN
RBNKRNBQ
RQNKRNBB
RNKBRQBN
RBKNQRBN
BRKBNQRN
RNNKRBBQ
RNQKRNBB
RNKBRQBN
RNKRNQBB
RNNKRQBB
RNKBRQBN
RKBNQBRN
RKBBQNNR
RKRNQNBB
RBBKQRNN
RNKBRQBN
RKBNQBRN
NBB...

result:

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

Test #6:

score: 0
Accepted
time: 135ms
memory: 3720kb

input:

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

output:

RNKBRQBN
RQBNNBKR
NNQRBBKR
BQRKNBRN
QRBKNBRN
RNKBRQBN
RQBNNBKR
NRBBQKNR
NRBKRBNQ
NRBKQBRN
RNKBRQBN
BBRNQNKR
NRNKBBRQ
NRBKNBRQ
RNKBRQBN
BBRNQNKR
NQBRKBNR
NRQNBKRB
BRQKNRNB
QRBKNNRB
RNKBRQBN
BBRNQNKR
BRNQKNRB
NRBKQNRB
RNKBRQBN
RQBNNBKR
NRBBQKNR
NBRQNKBR
NRBKNQRB
RNKBRQBN
RQBNNBKR
BBRNQKRN
BBNRKQNR
BRK...

result:

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

Test #7:

score: 0
Accepted
time: 122ms
memory: 3948kb

input:

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

output:

RNKBRQBN
RKBNQBRN
NBBQRKRN
RNBQNKRB
RBBQKRNN
RNKBRQBN
RKBNQBRN
RKBBQNNR
RKRNNBBQ
RBBNKRQN
RNKBRQBN
RQBNNBKR
NNQRBBKR
RBBNKRNQ
RNKBRQBN
RNBBQKNR
NRKBBRQN
RBNQKRBN
RBQNKRBN
RNKBRQBN
RNBBQKNR
NRKBBRQN
RBNQKRBN
RNKBRQBN
RKBNQBRN
RKQBBNNR
NRKRBBQN
RBNNKRBQ
RNKBRQBN
RNBBQKNR
RNBKQBRN
RNNBBKRQ
RQBBKRNN
RNK...

result:

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

Test #8:

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

input:

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

output:

RNKBRQBN
RKBNQBRN
QNNBBRKR
BRNBNQKR
QRNBKNBR
RNKBRQBN
RKBNQBRN
QNNBBRKR
BRKBNNQR
NRQBNKBR
NRQBKNBR
RNKBRQBN
RNBBQKNR
RNKNBRQB
NRNBKQBR
RNKBRQBN
RQBNNBKR
NNQRBBKR
RKNNBBRQ
QRNNKBBR
RNKBRQBN
RQBNNBKR
NNQRBBKR
NBRNBQKR
NRQNKBBR
RNKBRQBN
RQBNNBKR
NRBBQKNR
NBRQNKBR
RBNQBKNR
NRNQKBBR
RNKBRQBN
RQBNNBKR
BBR...

result:

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

Test #9:

score: 0
Accepted
time: 149ms
memory: 3868kb

input:

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

output:

RNKBRQBN
BBRNQNKR
BRNQNBKR
NBBRKNQR
QBBRKNNR
RNKBRQBN
RQBNNBKR
NRBBQKNR
NRBKRBNQ
NBBRKQNR
RNKBRQBN
BBRNQNKR
BRNQNBKR
NBBRKNQR
RNKBRQBN
RQBNNBKR
BBRNQKRN
QRKNBRNB
NRBBKNRQ
QBNRKNBR
RNKBRQBN
RQBNNBKR
BBRNQKRN
QRKNBRNB
NBQRKNBR
RNKBRQBN
RKBNQBRN
QNNBBRKR
BRKBNNQR
NBNRKQBR
RNKBRQBN
RQBNNBKR
NNQRBBKR
NBR...

result:

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

Test #10:

score: 0
Accepted
time: 135ms
memory: 3936kb

input:

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

output:

RNKBRQBN
BBRNQNKR
NBQRBNKR
BBRKNNRQ
BBRQNKNR
RNKBRQBN
BBRNQNKR
BBRNQKNR
RNKBRQBN
BBRNQNKR
NBBNQRKR
BBRNNKQR
RNKBRQBN
RQBNNBKR
NNQRBBKR
BQRKNBRN
BRKNNBRQ
BQRBNKNR
RNKBRQBN
RKBNQBRN
RBNQNKBR
NRKRNBBQ
RNNKBRQB
BNRBQKNR
RNKBRQBN
RKBNQBRN
QNNBBRKR
BNRBKNQR
BNRBNKQR
RNKBRQBN
BBRNQNKR
NBQRBNKR
BRQNNBKR
BBN...

result:

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

Test #11:

score: 0
Accepted
time: 135ms
memory: 3644kb

input:

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

output:

RNKBRQBN
RKBNQBRN
RBNQNKBR
BNNQRBKR
RQNBBNKR
RNKBRQBN
RNBBQKNR
RNBKQBRN
RNQBBNKR
RNKBRQBN
RBKNQRBN
NNQBRKBR
RNNBBQKR
RNKBRQBN
RQBNNBKR
RQBKNBNR
RQNNBBKR
RNKBRQBN
RKBNQBRN
NBBQRKRN
RNQNBBKR
RNKBRQBN
RKBNQBRN
RKQBBNNR
RBKNBRNQ
RNNKBBQR
RNNQBBKR
RNKBRQBN
RQBNNBKR
NNQRBBKR
RBNQBNKR
NRBBQNKR
BRQBNNKR
RNK...

result:

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

Extra Test:

score: 0
Extra Test Passed