QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491904#7179. Fischer's Chess Guessing Gameno_RED_no_DEADTL 506ms3760kbC++203.8kb2024-07-26 01:01:432024-07-26 01:01:44

Judging History

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

  • [2024-07-26 01:01:44]
  • 评测
  • 测评结果:TL
  • 用时:506ms
  • 内存:3760kb
  • [2024-07-26 01:01:43]
  • 提交

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 += cal(S[i], s);
    cnt /= (x + 1);

    if (cnt >= 2) return rand(0, 100);
    return 1;
}

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 <= 3; 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 = 2; i <= 0; 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: 12ms
memory: 3760kb

input:

GAME 1
1
1
1
5
0
8
END

output:

NRKRNQBB
BNRKNBQR
NBQNBRKR
RKRQBNNB
BBNNQRKR
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 506ms
memory: 3736kb

input:

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

output:

RBNKRQBN
QBRNKRBN
RNQKNRBB
RBNNBKQR
BBNNQRKR
RKRBBQNN
QRBBKNNR
NRNKQBBR
BNRBKRQN
BQRNKRNB
BBNRKNQR
RKRBBNQN
RKBBNNRQ
NRBBKNRQ
RQBKNNRB
RKNBRNBQ
BBNNQRKR
RKRBBNNQ
NRNQKRBB
RNBKQNRB
RQBBKNNR
RNKBRNBQ
BBNRKNRQ
RKRBQNBN
RBNQKRBN
QBBRKNRN
RNKBBRQN
NNRBKRBQ
BBNNQRKR
RKRBNQBN
BBRNQNKR
NRBNQKRB
BNRKRBNQ
RBN...

result:

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

Test #3:

score: -100
Time Limit Exceeded

input:

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

output:

RKNNQRBB
NQNBBRKR
NRKQBRNB
RBNKBQNR
BBNNQRKR
RKQBBNNR
RNKNBBRQ
NRBBNKRQ
RKBNRQNB
RKBRQBNN
BBNNQRKR
RKNBBQNR
RNNKBBQR
BNNRKBQR
RNQKNBBR
RBNNBKQR
BBNNQRKR
RKNBBNQR
RQBNNKRB
RKQBBNRN
RKQBNNBR
BRNBKRQN
BBRNKQNR
RQNBNKBR
RNBBNKQR
BBNNRQKR
RKNBQNBR
RKNBBQNR
RKQBBNNR
RBNKBQNR
RKNBNQBR
RNBQNKRB
NRKRNBBQ
RKQ...

result: