QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#647488#7179. Fischer's Chess Guessing Gameno_RED_no_DEADTL 189ms3992kbC++202.5kb2024-10-17 14:24:562024-10-17 14:25:10

Judging History

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

  • [2024-10-17 14:25:10]
  • 评测
  • 测评结果:TL
  • 用时:189ms
  • 内存:3992kb
  • [2024-10-17 14:24:56]
  • 提交

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 ++) {
            string chs; ld cur = 1e18;
            if (i == 1) chs = "NNRKRBBQ";
            else {
                for (auto x: cv) {
                    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 << 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(_);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3732kb

input:

GAME 1
1
2
1
2
0
8
END

output:

NNRKRBBQ
NRBBNQKR
QBBNRKNR
RQNBKNBR
QRKRNNBB
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 189ms
memory: 3992kb

input:

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

output:

NNRKRBBQ
NRBBNQKR
QBBNRKNR
RQNBKNBR
QRKRNNBB
RKRBBQNN
NNRKRBBQ
NRBBNQKR
BQNRKBNR
QBBNRKRN
RKRBBNQN
NNRKRBBQ
NRNQBBKR
RBQKNNBR
NBBRKNRQ
BNRBKNQR
RKRBBNNQ
NNRKRBBQ
NRNQBBKR
BBRKNQRN
BNQNRKRB
RBKRNNBQ
RKRBQNBN
NNRKRBBQ
NRNQBBKR
BBRKNQRN
BNRNKQRB
RKRBNQBN
NNRKRBBQ
NRNQKBBR
RNKBNRBQ
RKRBNNBQ
NNRKRBBQ
NRN...

result:

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

Test #3:

score: -100
Time Limit Exceeded

input:

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

output:

NNRKRBBQ
BRNBNKQR
RBBNNQKR
RKNNBRQB
RBNQBKRN
RKQBBNNR
NNRKRBBQ
BRNBNKQR
QBBRNKNR
BBNRKRQN
QRNNBKRB
RKNBBQNR
NNRKRBBQ
BRNBNKQR
BRQNNKRB
RKNBBNQR
NNRKRBBQ
NRBBNQKR
BQNBRNKR
BRKBNNRQ
RKQBNNBR
NNRKRBBQ
NRBBNQKR
QBBNRKNR
RQNBKNBR
RKNBQNBR
NNRKRBBQ
NRBBNQKR
NBNRBQKR
NRKBBQRN
RKNBNQBR
NNRKRBBQ
NRBBNQKR
BQN...

result: