QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#710377#7179. Fischer's Chess Guessing Gameno_RED_no_DEADTL 1808ms3920kbC++202.6kb2024-11-04 19:37:202024-11-04 19:37:22

Judging History

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

  • [2024-11-04 19:37:22]
  • 评测
  • 测评结果:TL
  • 用时:1808ms
  • 内存:3920kb
  • [2024-11-04 19:37:20]
  • 提交

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 ++) {
            string chs;

            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ìm đỉnh của đồ thị
                ll t = 0; for (int j = 0; j <= 8; j ++) t = max(t, pp[j]);
                // Chọn đồ thị có đỉnh bé nhất
                if (t < mx) mx = t, 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: 16ms
memory: 3644kb

input:

GAME 1
3
1
5
8
END

output:

RQKNBBRN
NRBKQBRN
RKNBBRQN
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 1774ms
memory: 3888kb

input:

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

output:

RQKNBBRN
NRBKQBRN
RKNBBRQN
RKRBBQNN
RQKNBBRN
NRBKQBRN
RKNBBRQN
RKRBBNQN
RQKNBBRN
RNNKQBBR
NNRQBKRB
QBRKBRNN
RKRBBNNQ
RQKNBBRN
RNNKQBBR
RBQKRNBN
RNQBKRBN
RKRBQNBN
RQKNBBRN
RNNKQBBR
RQBBNNKR
RKQBRNBN
RKRBNQBN
RQKNBBRN
RNBQKRNB
NNRBBKQR
RKNBQNBR
RKRBNNBQ
RQKNBBRN
RNKBBNRQ
QRKRBBNN
RKRQBBNN
RQKNBBRN
RNK...

result:

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

Test #3:

score: 0
Accepted
time: 1750ms
memory: 3696kb

input:

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

output:

RQKNBBRN
RNNKQBBR
RQBBNNKR
RNBBKNRQ
RKQBBNNR
RQKNBBRN
RNNKQBBR
RBQKRNBN
RKNBBQNR
RQKNBBRN
RNNKQBBR
RBQKRNBN
NRQKBBNR
RBBNQKNR
RKNBBNQR
RQKNBBRN
RNBQKRNB
NNRBBKQR
RKNBQNBR
RKNBNQBR
RKQBNNBR
RQKNBBRN
RNBQKRNB
NNRBBKQR
RKNBQNBR
RQKNBBRN
RNBQKRNB
NNRBBKQR
RKNBQNBR
RKNBNQBR
RQKNBBRN
RNKBBNRQ
QRKRBBNN
RKQ...

result:

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

Test #4:

score: 0
Accepted
time: 1790ms
memory: 3584kb

input:

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

output:

RQKNBBRN
RNKBBNRQ
QRKRBBNN
RQKNBBRN
RNKBBNRQ
QRKRBBNN
NRKRBBQN
RQKNBBRN
NRBKQBRN
NRKQBBNR
NRKRBBNQ
RQKNBBRN
RNNKQBBR
BRKNRNQB
BRKBRQNN
QRKRBNNB
RQKNBBRN
RNNKQBBR
BRKNRNQB
NRKRBQNB
RQKNBBRN
RNNKQBBR
BRKNRNQB
NRKRBNQB
RQKNBBRN
NRBKQBRN
NRKQBBNR
RQBKNBNR
BRKRNBQN
QRKRNBBN
RQKNBBRN
NRBKQBRN
NRNKBBRQ
NRK...

result:

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

Test #5:

score: 0
Accepted
time: 1762ms
memory: 3660kb

input:

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

output:

RQKNBBRN
RNKBBNRQ
RKQNRBBN
RQNKRBBN
RQKNBBRN
NRBKQBRN
NRKQBBNR
RKNRQBBN
RNQKRBBN
RQKNBBRN
RNNKQBBR
RNNKRBBQ
RQKNBBRN
RNNKQBBR
RBNKRQBN
RBNNKQBR
RQNKRNBB
RQKNBBRN
RNBQKRNB
RNBBNKQR
RNQKRNBB
RQKNBBRN
RNBQKRNB
RNBBNKQR
RNQKRNBB
RNNKRQBB
RQKNBBRN
RNNKQBBR
RBQKRNBN
RNQBKRBN
RNKQRNBB
RBBKQRNN
RQKNBBRN
RNN...

result:

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

Test #6:

score: 0
Accepted
time: 1808ms
memory: 3920kb

input:

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

output:

RQKNBBRN
NRBKQBRN
NRBQKBRN
QRBKNBRN
RQKNBBRN
NRBKQBRN
RQKNBBRN
RNNKQBBR
RQBBNNKR
RKBNQRNB
NRBKNBRQ
RQKNBBRN
RNBQKRNB
BNRKQBNR
RKNRQNBB
BRNQNKRB
QRBKNNRB
RQKNBBRN
RNBQKRNB
BNRKQBNR
NRBKQNRB
RQKNBBRN
RNBQKRNB
BNRKQBNR
RKNRQNBB
NBRNKRBQ
NRBKNQRB
RQKNBBRN
RNKBBNRQ
QRKRBBNN
RKQRBBNN
QRNKBBRN
RQKNBBRN
RNK...

result:

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

Test #7:

score: 0
Accepted
time: 1805ms
memory: 3660kb

input:

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

output:

RQKNBBRN
RNNKQBBR
NNRQBKRB
RKBNRNQB
RBBQKRNN
RQKNBBRN
NRBKQBRN
QRNNBKRB
RNQKBBNR
RBBNKRQN
RQKNBBRN
RNNKQBBR
NNRQBKRB
RKBBNRQN
RBBNKRNQ
RQKNBBRN
NRBKQBRN
RKNBBRQN
RNNQBBKR
RBQNKRBN
RQKNBBRN
RNNKQBBR
RBQKRNBN
RNQBKRBN
RBNQKRBN
RQKNBBRN
RNNKQBBR
RBQKRNBN
RNQNKRBB
RNQKBRNB
RBNNKRBQ
RQKNBBRN
NRBKQBRN
QRN...

result:

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

Test #8:

score: 0
Accepted
time: 1794ms
memory: 3728kb

input:

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

output:

RQKNBBRN
BBQRNNKR
QRBBNKNR
NRBBKNQR
QRNBKNBR
RQKNBBRN
BBQRNNKR
NRBBNQKR
NBRKNQBR
NRQBKNBR
RQKNBBRN
BBQRNNKR
BNRQKRNB
NRBKRNQB
NRNBKQBR
RQKNBBRN
RNNKQBBR
RBNKRQBN
RNKRQNBB
NQRKNBBR
QRNNKBBR
RQKNBBRN
RNNKQBBR
RBQKRNBN
NRQKBBNR
NRQNKBBR
RQKNBBRN
RNBQKRNB
BNRKQBNR
NRBKQNRB
NRNQKBBR
RQKNBBRN
RNBQKRNB
QNB...

result:

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

Test #9:

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

input:

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

output:

RQKNBBRN
BBQRNNKR
NBBRNKQR
NBBQRNKR
QBBRKNNR
RQKNBBRN
BBQRNNKR
NRBBNQKR
NBRKNQBR
NBBRKQNR
RQKNBBRN
BBQRNNKR
NBBRNKQR
NBBRKNQR
RQKNBBRN
BBQRNNKR
NBBRNKQR
BRQBNKNR
QBNRKNBR
RQKNBBRN
BBQRNNKR
BBNRNKQR
NBBRQNKR
NBQRKNBR
RQKNBBRN
BBQRNNKR
NRBBNQKR
NBNRKQBR
RQKNBBRN
RNBQKRNB
QNBRKNRB
NRBQKNRB
QNBRKBNR
RQK...

result:

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

Test #10:

score: -100
Time Limit Exceeded

input:

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

output:

RQKNBBRN
BBQRNNKR
NBBRNKQR
NBBQRNKR
BBRQNKNR
RQKNBBRN
RNBQKRNB
NNRBBKQR
NRBKNBQR
BBRNQKNR
RQKNBBRN
RNBQKRNB
BBRNQNKR
NBRNQKBR
BBRNNKQR
RQKNBBRN
RNBQKRNB
NNRBBKQR
NBRQBNKR
BNRKNBQR
BQRBNKNR
RQKNBBRN
BBQRNNKR
QRBBNKNR
NRBBKNQR
BNRBQKNR
RQKNBBRN
BBQRNNKR
NRBBNQKR
NBNRKQBR
BNRBNKQR
RQKNBBRN
RNNKQBBR
NNR...

result: