QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#710382#7179. Fischer's Chess Guessing Gameno_RED_no_DEADTL 1999ms3960kbC++202.6kb2024-11-04 19:38:122024-11-04 19:38:17

Judging History

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

  • [2024-11-04 19:38:17]
  • 评测
  • 测评结果:TL
  • 用时:1999ms
  • 内存:3960kb
  • [2024-11-04 19:38:12]
  • 提交

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;

            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: 21ms
memory: 3680kb

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: 1985ms
memory: 3960kb

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: 1931ms
memory: 3644kb

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: 1999ms
memory: 3640kb

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: -100
Time Limit Exceeded

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: