QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#647229#7179. Fischer's Chess Guessing Gameno_RED_no_DEADAC ✓184ms4180kbC++204.0kb2024-10-17 12:52:432024-10-17 12:52:44

Judging History

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

  • [2024-10-17 12:52:44]
  • 评测
  • 测评结果:AC
  • 用时:184ms
  • 内存:4180kb
  • [2024-10-17 12:52: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] = {"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 * log(x) * log(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);
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 4176kb

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: 103ms
memory: 4024kb

input:

GAME 1
6
4
4
5
0
8
GAME 2
4
4
2
4
0
8
GAME 3
5
3
5
8
GAME 4
3
3
1
0
1
8
GAME 5
4
3
5
5
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
4
2
1
8
GAME 10
4
4
4
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
3
1
8
GAME 16
2
4
1
2
0...

output:

RKNBBQNR
RKNBBNQR
RBNKBQNR
RKBBNQNR
BBNNQRKR
RKRBBQNN
RKNBBQNR
RKNQBBRN
RNKQBBNR
RKNNBRQB
BBNNQRKR
RKRBBNQN
RKNBBQNR
RKNNBBQR
RKBBQNNR
RKRBBNNQ
RKNBBQNR
NRNBQKBR
BNQBRKNR
QRNNBBKR
BBNNQRKR
RKRBQNBN
RKNBBQNR
RKNQBBRN
RKNBNRBQ
RKNRNQBB
BBNNQRKR
RKRBNQBN
RKNBBQNR
NRNBQKBR
RKNQRNBB
RBNKRQBN
BBNNQRKR
RKR...

result:

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

Test #3:

score: 0
Accepted
time: 159ms
memory: 3988kb

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
3
8
GAME 13
4
3
1
2
1
8
GAME 14
2
3
2
4
1
8
GAME 15
3
0
5
8
GAME 16
1
2
2
1
3
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: 3960kb

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
2
3
0
8
GAME 13
3
2
1
0
1
8
GAME 14
1
2
3
0
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: 179ms
memory: 4152kb

input:

GAME 1
2
1
0
2
2
8
GAME 2
1
2
1
0
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
3
3
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
4
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
NRBBQKRN
QBBNNRKR
BBNNRQKR
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: 177ms
memory: 4084kb

input:

GAME 1
0
1
3
2
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
3
4
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
NBBRNKRQ
BBQNRKRN
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: 183ms
memory: 4108kb

input:

GAME 1
2
4
1
4
2
8
GAME 2
1
0
5
2
3
8
GAME 3
2
3
1
4
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...

output:

RKNBBQNR
RBBQNNKR
NQBBRNKR
RBBKNQRN
BBNNQRKR
RBBQKRNN
RKNBBQNR
NRKQNBBR
RBBNQKRN
BBNRQKRN
BBNNQRKR
RBBNKRQN
RKNBBQNR
RBBQNNKR
QBNRNKBR
RKBNNRQB
BBNNQRKR
RBBNKRNQ
RKNBBQNR
NRKQNBBR
BQNRNKRB
QBBNRNKR
BBNNQRKR
RBQNKRBN
RKNBBQNR
RBBQNNKR
QBNRNKBR
BBNNQRKR
BBNNRKQR
RBNQKRBN
RKNBBQNR
RBBQNNKR
NRQBNKBR
BNR...

result:

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

Test #8:

score: 0
Accepted
time: 179ms
memory: 4180kb

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
5
3
2
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
GAM...

output:

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

result:

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

Test #9:

score: 0
Accepted
time: 162ms
memory: 4176kb

input:

GAME 1
2
4
3
4
2
8
GAME 2
3
2
0
8
GAME 3
1
2
2
2
3
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
4
1
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
4
5
1
8
GAME 14
1
0
8
GAME 15
1
1
3
0
2
8
GAME 16
2
2
2
2
4
8...

output:

RKNBBQNR
RBBQNNKR
NQBBRNKR
BBNRQNKR
BBNNQRKR
QBBRKNNR
RKNBBQNR
NRNBQKBR
RKNQRNBB
NBBRKQNR
RKNBBQNR
NRKQNBBR
NRBBQKRN
BRNQKNRB
BBNNRKQR
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: 171ms
memory: 3940kb

input:

GAME 1
2
4
1
2
3
8
GAME 2
2
2
2
3
5
8
GAME 3
1
2
1
4
4
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
5
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...

output:

RKNBBQNR
RBBQNNKR
NQBBRNKR
RBBKNQRN
BBNNQRKR
BBRQNKNR
RKNBBQNR
RBBQNNKR
NRQBNKBR
NQRNBBKR
BBNNQRKR
BBRNQKNR
RKNBBQNR
NRKQNBBR
NRBBQKRN
QBBNNRKR
BBNNQRKR
BBRNNKQR
RKNBBQNR
NRNBQKBR
BNQBRKNR
BBNQRKNR
BBNNQRKR
BQRBNKNR
RKNBBQNR
NRNBQKBR
NRKBBNQR
BNNBQRKR
BBNNQRKR
BNRBQKNR
RKNBBQNR
RBBQNNKR
NRQBNKBR
BNR...

result:

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

Test #11:

score: 0
Accepted
time: 184ms
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
4
5
4
8
GAME 5
3
1
1
2
2
8
GAME 6
4
5
3
3
3
8
GAME 7
2
4
4
8
GAME 8
3
5
5
8
GAME 9
4
1
3
8
GAME 10
1
4
5
8
GAME 11
2
4
2
4
4
8
GAME 12
2
2
2
4
6
8
GAME 13
2
5
3
3
2
8
GAME 14
2
4
6
5
3
8
GAME 15
3
4
4
2
2
8
GAME 16
1
4
6
5
3
8
GAME ...

output:

RKNBBQNR
RKNNBBQR
RBKNBQNR
RKNQBRNB
BBNNQRKR
RQNBBNKR
RKNBBQNR
RKNQBBRN
QRNBBNKR
NQNBBRKR
BBNNQRKR
RNQBBNKR
RKNBBQNR
RKNBBNQR
RKNBBQRN
RKNBBRNQ
BBNNQRKR
RNNBBQKR
RKNBBQNR
RKNQBBRN
RNKQBBNR
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