QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#714020#7179. Fischer's Chess Guessing Gameno_RED_no_DEADTL 1982ms3920kbC++202.6kb2024-11-05 21:15:442024-11-05 21:15:44

Judging History

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

  • [2024-11-05 21:15:44]
  • 评测
  • 测评结果:TL
  • 用时:1982ms
  • 内存:3920kb
  • [2024-11-05 21:15:44]
  • 提交

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 ++) {
if (i == 7) {cout << 1 / 0;}
            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(_);
}

詳細信息

Test #1:

score: 100
Accepted
time: 22ms
memory: 3900kb

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: 1969ms
memory: 3920kb

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: 1927ms
memory: 3920kb

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: 1982ms
memory: 3688kb

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: 1973ms
memory: 3688kb

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

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: