QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491929#7179. Fischer's Chess Guessing Gameno_RED_no_DEADTL 514ms4036kbC++203.7kb2024-07-26 01:26:322024-07-26 01:26:33

Judging History

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

  • [2024-07-26 01:26:33]
  • 评测
  • 测评结果:TL
  • 用时:514ms
  • 内存:4036kb
  • [2024-07-26 01:26:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e6 + 1;
const ll M = 1e9 + 7;

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

string P = "BRKBNQRN";
string Q = "KNNBBRRQ";
string S[5];
ll T[] = {(ll)100, (ll)300, (ll)1500, (ll)10000};
vector<string> v, res;
ll val[N];

ll cal(string &s, string &t) {
    ll res = 0;
    for (int i = 0; i <= 7; i ++)
        if (s[i] == t[i]) res ++;
    return res;
}

ll check(ll x, string &s) {
    ll cnt = 0;
    for (int i = 0; i < x; i ++) cnt += (1LL << cal(S[i], s)) * 100;
    return cnt;
}

void doTest(ll testID) {
    while (true) {
        bool nxt = 0;
        string tmp; cin >> tmp;
        if (tmp == "END") return;
        cin >> tmp;

        res.clear();
        for (auto x: v) res.push_back(x);

        /* BEGIN MESS 1*/
        for (int i = 0; i <= 2; i ++) {
            ll cnt = -1, tmp = 0;
            for (int j = 0; j < T[i]; j ++) {
                string cur = res[rand(0, res.size() - 1)]; tmp = 0;
                for (auto y: res) tmp += check(i, cur);
                if (tmp > cnt) {cnt = tmp; S[i] = cur;}
            }
            cout << S[i] << endl; 
            cin >> val[i]; if (val[i] == 8) {nxt = 1; break;}

            vector<string> newRes;
            for (auto x: res) if (cal(x, S[i]) == val[i]) newRes.push_back(x);
            res = newRes;
            // cout << "Debug: " << res.size() << endl;
        }
        if (nxt) continue;

        /* BEGIN MESS 2*/
        for (int i = 3; i <= 3; i ++) {
            ll cnt = 0, tmp = 0;
            for (int j = 0; j < T[i]; j ++) {
                string cur = res[rand(0, res.size() - 1)];
                set<ll> s; for (auto y: res) s.insert(cal(cur, y));
                if (s.size() > cnt) {cnt = s.size(); S[i] = cur;}
            }
            cout << S[i] << endl; 
            cin >> val[i]; if (val[i] == 8) {nxt = 1; break;}
            
            vector<string> newRes;
            for (auto x: res) if (cal(x, S[i]) == val[i]) newRes.push_back(x);
            res = newRes;
            // cout << "Debug: " << res.size() << endl;
        }
        if (nxt) continue;

        /* BEGIN MESS 3*/
        for (int i = 4; i <= 4; i ++) {
            ll cnt = 0;
            for (auto x: v) {
                set<ll> s; for (auto y: res) s.insert(cal(x, y));
                if (s.size() > cnt) {cnt = s.size(); S[4] = x;}
            }
            cout << S[i] << endl; 
            cin >> val[i]; if (val[i] == 8) {nxt = 1; break;}
            
            vector<string> newRes;
            for (auto x: res) if (cal(x, S[i]) == val[i]) newRes.push_back(x);
            res = newRes;
        }
        if (nxt) break;

        /*BEGIN MESS 4*/
        // cout << "??? " << res.size() << endl;
        cout << res[0] << endl;
        cin >> val[5];
    }
}

signed main() {
    set<string> s;
    string T = "KNNBBRRQ";
    sort(T.begin(), T.end());
    do {
        vector<ll> b, r, k;
        for (int i = 0; i <= 7; i ++) if (T[i] == 'B') b.push_back(i);
        for (int i = 0; i <= 7; i ++) if (T[i] == 'K') k.push_back(i);
        for (int i = 0; i <= 7; i ++) if (T[i] == 'R') r.push_back(i);
        if ((b[1] - b[0]) % 2 == 0) continue;
        if (r[0] > k[0] || r[1] < k[0]) continue;
        s.insert(T);
    } while(next_permutation(T.begin(), T.end()));
    for (auto x: s) v.push_back(x);

    ios_base::sync_with_stdio(0); cin.tie(0);

    int test = 1; 
    // cin >> test;
    for (int _ = 1; _ <= test; _ ++) doTest(test);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 3756kb

input:

GAME 1
3
3
2
2
0
8
END

output:

RQNKBBRN
RBNNBQKR
RQNBKNBR
BBNRKQRN
BBNNQRKR
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 514ms
memory: 4036kb

input:

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

output:

QRBNKBRN
QNNBRKBR
NBBRNQKR
NRNKBRQB
BBNQRKRN
RKRBBQNN
QRBBNKRN
BRNBKNQR
BRKQNBNR
RKRBBNQN
NBRKQRBN
NNBQRKRB
BBNRNQKR
RKRBBNNQ
RKQBRNBN
RKQBNNBR
RKNBRNBQ
RKQNRNBB
BBNNQRKR
RKRBQNBN
RQNKNBBR
RNKNBBQR
RKNQRNBB
RKQBNRBN
BBNNQRKR
RKRBNQBN
NNBRKBRQ
QRNBBKRN
RBNKNRBQ
RBNQKNBR
BBNRKQRN
RKRBNNBQ
NBQRBKRN
BNN...

result:

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

Test #3:

score: -100
Time Limit Exceeded

input:

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

output:

BBRKRNNQ
BRNKNRQB
RNKNRBBQ
RKQBBNNR
QBBNRNKR
RKQRNNBB
NBQRBKRN
NRKQNBBR
RKNBBRNQ
RKNBBQNR
RKRNQBBN
NRBBQKRN
RKBRNNQB
RKNBBNQR
NBRKBNQR
RNKBBNRQ
RBNQBKRN
RQBBNNKR
BBNNQRKR
RKQBNNBR
RKRBQNBN
RKBBQNRN
RKNBQNBR
BNNQRKRB
RQNNKBBR
RNQNBBKR
QRNKNBBR
BBNNQRKR
RKNBNQBR
NQNBBRKR
RNKBNQBR
NRNKRQBB
RKQBBNRN
BBN...

result: