QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491900#7179. Fischer's Chess Guessing Gameno_RED_no_DEADTL 613ms4036kbC++203.8kb2024-07-26 00:59:162024-07-26 00:59:16

Judging History

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

  • [2024-07-26 00:59:16]
  • 评测
  • 测评结果:TL
  • 用时:613ms
  • 内存:4036kb
  • [2024-07-26 00:59:16]
  • 提交

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 <= 1; 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 <= 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: 3868kb

input:

GAME 1
3
3
2
8
END

output:

RNKBBNQR
BNRBKRQN
QNRBNKBR
RKRBBQNN

result:

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

Test #2:

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

input:

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

output:

QNRNKBBR
BBRKQRNN
BRNBKRNQ
RNQKBRNB
BBNNQRKR
RKRBBQNN
RQBNKRNB
BNRBKNQR
BBRQKNRN
RKRBBNQN
NRBKRBNQ
RBNKRQBN
BRQNKBRN
RKBBQNNR
BBNNQRKR
RKRBBNNQ
NRBKRQNB
RNKBQRBN
RQNBKRBN
RNNBQKBR
BBNNQRKR
RKRBQNBN
RBKNBNRQ
RKNQNBBR
RKQBNRBN
RKNBQRBN
BBNNQRKR
RKRBNQBN
RNQNBBKR
RBBKNRNQ
RKBQNNRB
RKRBNNBQ
NRKBBQRN
NBR...

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
0
8
GAME 2
1
1
1
6
2
8
GAME 3
2
2
2
0
3
8
GAME 4
3
6
8
GAME 5
2
2
6
8
GAME 6
3
1
2
3
3
8
GAME 7
1
4
3
5
2
8
GAME 8
0
5
4
2
2
8
GAME 9
4
2
1
8
GAME 10
4
3
5
2
2
8
GAME 11
1
2
2
6
2
8
GAME 12
3
3
3
4
4
8
GAME 13
0
0
2
8
GAME 14
1
3
3
5
1
8
GAME 15
3
4
1
5
1
8
GAME 16
0
1
1
4
2
8
GAME 17
2
0...

output:

RQKNBBRN
BRQBKNRN
BBNRQKRN
RKQBBNNR
BNNRKBRQ
QRKNNBBR
NRBBQKRN
RKNBBNQR
BBNNQRKR
RKNBBQNR
RNBKRBQN
RNKBNRBQ
RKBNNQRB
BNRNKBRQ
BBNRNKQR
RKNBBNQR
RNKRNQBB
RBQKNNBR
RKQBNNBR
RKBQNBRN
RBQNKRBN
RKNBRNBQ
RKNBQNBR
RQNKBBNR
NBRQBKNR
RNBKRQNB
RNKNQBBR
BBNRKQNR
RKNBNQBR
NBRKNQBR
RBQNBKRN
RBKQBRNN
RKRNBBQN
BBN...

result: