QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#647445#7179. Fischer's Chess Guessing Gameno_RED_no_DEADRE 174ms4032kbC++203.7kb2024-10-17 14:15:242024-10-17 14:15:25

Judging History

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

  • [2024-10-17 14:15:25]
  • 评测
  • 测评结果:RE
  • 用时:174ms
  • 内存:4032kb
  • [2024-10-17 14:15:24]
  • 提交

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 = fuck[rand(0, 3)];
            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: 100
Accepted
time: 4ms
memory: 3728kb

input:

GAME 1
2
2
1
4
8
END

output:

NRBBNQKR
RBBNQKNR
RQNKNBBR
RKBBRNQN
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 174ms
memory: 4032kb

input:

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

output:

NRNBBQKR
RNBBQNKR
RBNQBKNR
NRBQKBNR
RKRBBQNN
NRNQBBKR
RKQBNNBR
RKQBBRNN
RKNBQRBN
RKRBBNQN
NRBBNQKR
RKNNQBBR
BRNNKRQB
NNRKRBBQ
RBKRNNBQ
RKRBBNNQ
NRBQNBKR
BNRNKRQB
RKQBBRNN
RBNKBRNQ
RKRBQNBN
NRNBBQKR
RBQNBKNR
NRKNQRBB
NNBRKBQR
RKNBRNBQ
RKRBNQBN
NRBQNBKR
RKNBQNBR
RKQBBNNR
RKBBQNRN
RKRBNNBQ
NRNQBBKR
RNB...

result:

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

Test #3:

score: -100
Runtime Error

input:

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

output:

NRBBNQKR
RBBNQKNR
BBNRQNKR
RNQNBBKR
BRQNKBNR
RKQBBNNR
NRNQBBKR
RNBNQBKR
RQNKBBRN
NRBKRBQN
RKNBBQNR
NRNBBQKR
NRKBRQBN
NBRQBNKR
BBNRNQKR
RKNBBNQR
NRNQBBKR
RKQBNNBR
NRBBNQKR
RBBNQKNR
BBNRQNKR
NBNRBKQR
BRNKQBNR
RKNBQNBR
NRBQNBKR
QBBRKNNR
RNKBNQBR
RKNBNQBR
NRBQNBKR
QBBRKNNR
RBBNNKRQ
RQBKRBNN
RKQNBBNR
NRB...

result: