QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#647235#7179. Fischer's Chess Guessing Gameno_RED_no_DEADAC ✓177ms4044kbC++204.0kb2024-10-17 12:54:072024-10-17 12:54:07

Judging History

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

  • [2024-10-17 12:54:07]
  • 评测
  • 测评结果:AC
  • 用时:177ms
  • 内存:4044kb
  • [2024-10-17 12:54:07]
  • 提交

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] = {"RKNBBQNR"};
ll T[] = {(ll)0, (ll)300, (ll)15000, (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 <= 7; i ++) {
        ll tmp = 0;
        for (int j = 0; j < x; j ++)
            tmp += (S[j][i] == s[i]);
        cnt += tmp * 1e9;
    }
    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 <= -1; i ++) {
            ll cnt = -1, tmp = 0;
            for (int j = 0; j < min(T[i], (ll)res.size()); j ++) {
                string cur = res[j]; 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 = 0; i <= 3; i ++) {
            ll cnt = 1e18, tmp = 0;
            for (int j = 0; j < min(T[i], (ll)res.size()); j ++) {
                string cur = res[j];
                map<ll, ll> m; for (auto y: res) m[cal(cur, y)] ++;
                tmp = 0; for (auto [l, x]: m) tmp += x *sqrt(x);
                if (tmp < cnt) {cnt = tmp; S[i] = cur;}
            }
            val[i] = cal(P, S[i]);
            // cout << "Debug: " << i << ' ' << S[i] << endl;

            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[i] = 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) continue;

        /*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: 1ms
memory: 3980kb

input:

GAME 1
6
4
4
5
0
8
END

output:

RKNBBQNR
RKNBBNQR
RBNKBQNR
RKBBNQNR
BBNNQRKR
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 104ms
memory: 4044kb

input:

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

output:

RKNBBQNR
RKNBBNQR
RBNKBQNR
RKBBNQNR
BBNNQRKR
RKRBBQNN
RKNBBQNR
RKNQBBRN
RNKBBQRN
RKRBBNQN
RKNBBQNR
RKNNBBQR
RKBBQNNR
RKRBBNNQ
RKNBBQNR
NRNBQKBR
BNQBRKNR
QRNNBBKR
BBNNQRKR
RKRBQNBN
RKNBBQNR
RKNQBBRN
RBNKBNQR
RKBBQRNN
BBNNQRKR
RKRBNQBN
RKNBBQNR
NRNBQKBR
RKNQRNBB
RBNKRQBN
BBNNQRKR
RKRBNNBQ
RKNBBQNR
RKN...

result:

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

Test #3:

score: 0
Accepted
time: 154ms
memory: 3968kb

input:

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

output:

RKNBBQNR
RKNBBNQR
RKQBBNNR
RKNBBQNR
RKNBBQNR
RKNBBNQR
RKNBBQNR
RKNQBBRN
QRNBBNKR
RBQKBNNR
BBNNQRKR
RKQBNNBR
RKNBBQNR
RKNNBBQR
RBKNBQNR
RKNBBNRQ
BBNNQRKR
RKNBQNBR
RKNBBQNR
RKNBBNQR
RKNBBQRN
RKNBBRNQ
BBNNQRKR
RKNBNQBR
RKNBBQNR
RKNNBBQR
RKQNBBNR
RKNBBQNR
RKNBBNQR
RKNBBQRN
RKNQBBNR
RKNBBQNR
RKNNBBQR
RKN...

result:

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

Test #4:

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

input:

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

output:

RKNBBQNR
RBBQNNKR
QNRBBKRN
BNRBKRNQ
BBNNQRKR
QRKRBBNN
RKNBBQNR
NRKQNBBR
NRBNQBKR
BNRQNBKR
BBNNQRKR
NRKRBBQN
RKNBBQNR
RBBQNNKR
QNRBBKRN
BRNNKQRB
BBNNQRKR
NRKRBBNQ
RKNBBQNR
RBBQNNKR
BRKBNRNQ
BRQNKBNR
BBNNQRKR
QRKRBNNB
RKNBBQNR
NRNBQKBR
RKNQRNBB
QNNRBBKR
BBNNRKQR
NRKRBQNB
RKNBBQNR
NRKQNBBR
RBKQRNBN
BRK...

result:

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

Test #5:

score: 0
Accepted
time: 171ms
memory: 3708kb

input:

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

output:

RKNBBQNR
RBBQNNKR
BRKBNRNQ
NNRKBBQR
BBNNRKRQ
RQNKRBBN
RKNBBQNR
NRKQNBBR
BRKNQRNB
NBRQBKRN
BBNNRKQR
RNQKRBBN
RKNBBQNR
RBBQNNKR
BRKBNRNQ
RNNKQRBB
BBNNQRKR
RNNKRBBQ
RKNBBQNR
RBBQNNKR
NRQBNKBR
BNRQKBNR
BBNNQRKR
RQNKRNBB
RKNBBQNR
NRKQNBBR
BQNRNKRB
RNBKQBRN
BBNNRKQR
RNQKRNBB
RKNBBQNR
NRNBQKBR
RKNQRNBB
RKN...

result:

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

Test #6:

score: 0
Accepted
time: 170ms
memory: 3792kb

input:

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

output:

RKNBBQNR
NRKNQRBB
NNBRKBRQ
BBRNKNRQ
BBNNQRKR
QRBKNBRN
RKNBBQNR
NRKNQRBB
BRQNNKRB
NRBKQBRN
RKNBBQNR
NRKNQRBB
NRBQKBRN
BRKQNBRN
BBNNQRKR
NRBKNBRQ
RKNBBQNR
NRKNQRBB
NRBQKBRN
NBBNRKRQ
BBNNRKQR
QRBKNNRB
RKNBBQNR
NRKNQRBB
NNRQKRBB
NRBKQNRB
RKNBBQNR
NRKQNBBR
RBKQRNBN
BQRNNBKR
BBNNRKQR
NRBKNQRB
RKNBBQNR
RBB...

result:

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

Test #7:

score: 0
Accepted
time: 176ms
memory: 3740kb

input:

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

output:

RKNBBQNR
RBBQNNKR
BRQBNNKR
RBBQKRNN
RKNBBQNR
NRKQNBBR
RBBNQKRN
BBNRQKRN
BBNNQRKR
RBBNKRQN
RKNBBQNR
RBBQNNKR
QBNRNKBR
RBBKQRNN
BBNNQRKR
RBBNKRNQ
RKNBBQNR
NRKQNBBR
BQNRNKRB
QBBNRNKR
BBNNQRKR
RBQNKRBN
RKNBBQNR
RBBQNNKR
QBNRNKBR
BBNNQRKR
BBNNRKQR
RBNQKRBN
RKNBBQNR
RBBQNNKR
NRQBNKBR
BNRQKBNR
BBNNQRKR
RBN...

result:

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

Test #8:

score: 0
Accepted
time: 175ms
memory: 3904kb

input:

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

output:

RKNBBQNR
NRNBQKBR
QRNBKNBR
RKNBBQNR
RBBQNNKR
NRQBNKBR
NQRBNKBR
BBNNQRKR
NRQBKNBR
RKNBBQNR
RKNQBBRN
RQBBNKNR
BNNBRQKR
BBNNQRKR
NRNBKQBR
RKNBBQNR
RBBQNNKR
BRKBNRNQ
RNNKQRBB
BBNRKRQN
QRNNKBBR
RKNBBQNR
NRKQNBBR
BRKNNBQR
NRQNKBBR
RKNBBQNR
RBBQNNKR
NRQBNKBR
BNRBNKQR
BBNNQRKR
NRNQKBBR
RKNBBQNR
NRKQNBBR
BQN...

result:

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

Test #9:

score: 0
Accepted
time: 156ms
memory: 3792kb

input:

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

output:

RKNBBQNR
RBBQNNKR
BRQBNNKR
NBBNRQKR
BBNQRKNR
QBBRKNNR
RKNBBQNR
NRNBQKBR
RKNQRNBB
NBBRKQNR
RKNBBQNR
NRKQNBBR
BRKNQRNB
NBRQBKRN
BBNNQRKR
NBBRKNQR
RKNBBQNR
RBBQNNKR
QBNRNKBR
BBNRNKQR
BBNNQRKR
QBNRKNBR
RKNBBQNR
NRKQNBBR
RBKQRNBN
BBRQNNKR
BBNNQRKR
NBQRKNBR
RKNBBQNR
NRNBQKBR
NRKBBNQR
BNNBQRKR
BBNNQRKR
NBN...

result:

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

Test #10:

score: 0
Accepted
time: 164ms
memory: 3764kb

input:

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

output:

RKNBBQNR
RBBQNNKR
BRQBNNKR
BBRQKNNR
BBNNQRKR
BBRQNKNR
RKNBBQNR
RBBQNNKR
NRQBNKBR
BBRNQKNR
RKNBBQNR
NRKQNBBR
BRKNQRNB
BBRNNKQR
RKNBBQNR
NRNBQKBR
BNQBRKNR
BBNQRKNR
BBNNQRKR
BQRBNKNR
RKNBBQNR
NRNBQKBR
NRKBBNQR
BNNBQRKR
BBNNQRKR
BNRBQKNR
RKNBBQNR
RBBQNNKR
NRQBNKBR
BNRBNKQR
RKNBBQNR
NRNBQKBR
RKNQRNBB
NBB...

result:

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

Test #11:

score: 0
Accepted
time: 177ms
memory: 3908kb

input:

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

output:

RKNBBQNR
RKNNBBQR
RBKNBQNR
RKNQBRNB
BBNNQRKR
RQNBBNKR
RKNBBQNR
RKNQBBRN
QRNBBNKR
NQNBBRKR
BBNNQRKR
RNQBBNKR
RKNBBQNR
RKNBBNQR
RKNBBQRN
RKNBBRNQ
BBNNQRKR
RNNBBQKR
RKNBBQNR
RKNQBBRN
RNKBBQRN
RBNQBNKR
BBNNQRKR
RQNNBBKR
RKNBBQNR
NRNBQKBR
RKBBNRQN
RBNKBNRQ
BBNNRKQR
RNQNBBKR
RKNBBQNR
RKNQBBRN
RBNKBQRN
RKQ...

result:

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

Extra Test:

score: 0
Extra Test Passed