QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#647154#7179. Fischer's Chess Guessing Gameno_RED_no_DEADRE 1ms3948kbC++202.7kb2024-10-17 12:07:452024-10-17 12:07:53

Judging History

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

  • [2024-10-17 12:07:53]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3948kb
  • [2024-10-17 12:07: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;

vector<string> v;
set<string> s;
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;
        s.insert(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;
}

void doTest(ll testID) {
    backtrack(1, 0, 0, 0, 0, 0);
    for (auto x: s) v.push_back(x);

    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 cur = -1, me = -1;
            if (i == 1) chs = cv[0];
            else {
                for (auto x: cv) {
                    ll tmp = 1e18; for (auto y: cv) tmp = min(tmp, get(x, y));
                    if (tmp > cur) cur = tmp, chs = x;
                }
                
                for (auto x: cv) {
                    ll tmp = 1e18; for (auto y: cv) tmp = min(tmp, get(x, y));
                    if (tmp == cur) {
                        ll e = 0; for (auto y: cv) e += get(x, y) * log2(get(x, y)) * log2(get(x, y));
                        if (e > me) me = e, 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;

            // cout << cv.size() << endl;
        }
    }
}

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: 1ms
memory: 3948kb

input:

GAME 1
0
1
4
1
8
END

output:

BBNNQRKR
NNBBRKRQ
RNKRBQNB
NRKRBNQB
RKRBBQNN

result:

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

Test #2:

score: -100
Runtime Error

input:

GAME 1
0
1
4
1
8
GAME 2
0
1
2
8
GAME 3
0
2
4
3
2
8
GAME 4
1
2
2
2
2
1

output:

BBNNQRKR
NNBBRKRQ
RNKRBQNB
NRKRBNQB
RKRBBQNN
BBNNQRKR
NNBBRKRQ
RNKRBQNB
RKRBBNQN
BBNNQRKR
NNBBRKRQ
RQKBBNRN
NQRKBNRB
RNQKBBRN
RKRBBNNQ
BBNNQRKR
BNQBRKRN
BQRKNNRB
RQBNKBRN
RNQKNBBR
BRKRNBQN

result: