QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#647443#7179. Fischer's Chess Guessing Gameno_RED_no_DEADRE 205ms3848kbC++203.7kb2024-10-17 14:13:492024-10-17 14:13:50

Judging History

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

  • [2024-10-17 14:13:50]
  • 评测
  • 测评结果:RE
  • 用时:205ms
  • 内存:3848kb
  • [2024-10-17 14:13:49]
  • 提交

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 = v[rand(0, v.size() - 1)];
            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: 1ms
memory: 3740kb

input:

GAME 1
0
5
4
4
8
END

output:

BRKNRNQB
RKBBNQRN
RKNBNQBR
RKBBNRNQ
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 205ms
memory: 3744kb

input:

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

output:

BRQBNKNR
RBBNNQKR
NNQRBBKR
NRBKNRQB
RKNBQNBR
RKRBBQNN
RBNNKRBQ
BRNBNQKR
NRKRBBNQ
QBBRNKRN
RKRBBNQN
QRBBNKRN
RKQNNBBR
QNNRBBKR
RBQKBRNN
RBKRQNBN
RKRBBNNQ
NRBKNQRB
RNKBQRBN
RBKRQNBN
RKRBQNBN
RNKQBBNR
BNRNKQRB
BBRKNNQR
BBNRKRNQ
NRQKBNRB
RKRBNQBN
RKNQBBRN
RQKNNBBR
NRBQNBKR
RBQKNRBN
RBQNBKNR
RKRBNNBQ
RKN...

result:

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

Test #3:

score: 0
Accepted
time: 201ms
memory: 3848kb

input:

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

output:

NRKQRNBB
RBQNBNKR
BBRNQNKR
RBQKBNRN
RKQBBNNR
NQRKBBRN
RNBNQBKR
RKNBQRBN
RKNNBRQB
RKNBBQNR
QRKNBNRB
RBQNKNBR
NRBNKBQR
RBBNQKRN
NBRQBNKR
RKNBBNQR
BRNBNKRQ
RBNKNQBR
NBRQNKBR
RBKRNNBQ
RKQBNNBR
NRQNBBKR
RQKBNNBR
RQBBKNNR
RKNBQNBR
NBBRKQRN
NRKBBNQR
QRNNBKRB
RBNKQNBR
BBNQRNKR
RKNBNQBR
BBRNQNKR
BRNBKQNR
BBN...

result:

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

Test #4:

score: -100
Runtime Error

input:

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

output:

QRKNRNBB
NRKBNQBR
BRNNKQRB
QNRKNRBB
QRKRBBNN
RBBNNKQR
RKQBBNRN
NRKNBQRB
NRBQKNRB
BRKNQBRN
NRKRBBQN
QBRKBNRN
RKQBNNBR
BNNQRKRB
NBBRKRNQ
NRKRBBNQ
RNBBQKNR
BRQKNRNB
NRKNQRBB
NNRKBRQB
QRKRBNNB
RBQNKRBN
NNRBBQKR
NRNBBKRQ
NRKRBQNB
RNBKQBNR
NRKQNRBB
NBRQKRBN
NRKNBQRB
NRKRBNQB
BNRNKRQB
NRBBQKNR
RBKRBNNQ
RBN...

result: