QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#647451#7179. Fischer's Chess Guessing Gameno_RED_no_DEADRE 0ms0kbC++203.7kb2024-10-17 14:16:582024-10-17 14:16:58

Judging History

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

  • [2024-10-17 14:16:58]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-17 14:16:58]
  • 提交

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;
}

mt19937_64 rng(static_cast<ll>(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count()));

ll rand(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

map<string, ll> m;

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

    ll cc = 0;
    ll test = 0;
    ll ok = 0;
    while (true) {
        string s; ll num; cin >> s; if (s == "END") return; cin >> num;
        m.clear();
        // /*#TEST*/ string real = v[cc]; cc++; ok ++; if (cc == v.size()) break; 
        // cout << "Real: " << real << endl;

        vector<string> cv = v; 
        for (int i = 1;; i ++) {
            /*#TEST*/ if (i == 7) {
                // cout << real << endl;
                // ok --; break;
            }
            assert(i <= 6);
            
            const string fuck[] = {"NRNQBBKR", "NRBBNQKR", "NRBQNBKR", "NRNBBQKR"};

            string chs; ld cur = 1e18;
            if (i == 1) chs = "NNRKRBB";
            else {
                // m["NRBBNQKR"] ++; m["NRBQNBKR"] ++; m["NRNBBQKR"] ++;
                for (auto x: cv) {
                    if (m.count(x)) continue; map<ll, ll> pp;
                    for (auto y: cv) pp[get(x, y)] ++;
                    ld avg = 0, j = 0; for (auto [x, y]: pp) avg += y, j ++; avg /= pp.size();
                    ld tmp = 0; for (auto [x, y]: pp) tmp += (ld)(y - avg) * (y - avg) / pp.size();
                    if (tmp < cur) cur = tmp, chs = x;
                }
                // cout << cur << endl;
            }
            // if (i == 1) {cout << chs << endl; return;}
            cout << chs << endl;
            m[chs] ++;
            
            ll req; 
            cin >> req; 
            // /*#TEST*/ req = get(real, chs);
            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;
        }
        // /*#TEST*/ test ++; cout << "Accept test: " << test << endl;
    }
    // cout << "Total: " << ok << 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: 0
Runtime Error

input:

GAME 1

output:

NNRKRBB

result: