QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#491912#7179. Fischer's Chess Guessing Gameno_RED_no_DEADTL 454ms3964kbC++203.7kb2024-07-26 01:11:402024-07-26 01:11:41

Judging History

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

  • [2024-07-26 01:11:41]
  • 评测
  • 测评结果:TL
  • 用时:454ms
  • 内存:3964kb
  • [2024-07-26 01:11:40]
  • 提交

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

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 3800kb

input:

GAME 1
5
3
5
4
0
8
END

output:

RKNBRQBN
RKNRQBBN
RKBBNQRN
RKBBRNQN
BBNNQRKR
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 454ms
memory: 3964kb

input:

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

output:

RKBNRBQN
RKNNBQRB
RBNNBKQR
RKRBBQNN
NRBQKBNR
RBKNBRQN
RQKBNRBN
BBRKNRQN
BBNNQRKR
RKRBBNQN
BBRKNQNR
RNNBBQKR
NBQRBNKR
BQNNRBKR
BBNNQRKR
RKRBBNNQ
BQNRNBKR
NRBBKNRQ
NRQKBRNB
QBBNRKRN
BBNNQRKR
RKRBQNBN
BRNBNKRQ
RKNBQRBN
RKBBNRQN
RQKBNRBN
BBNNQRKR
RKRBNQBN
NRKBBNRQ
NRBBNQKR
NRKNQRBB
NBRKBQRN
BBNNQRKR
RKR...

result:

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

Test #3:

score: -100
Time Limit Exceeded

input:

GAME 1
1
3
4
4
1
8
GAME 2
3
1
3
8
GAME 3
1
6
5
8
GAME 4
6
5
8
GAME 5
1
2
4
2
3
8
GAME 6
2
6
5
8
GAME 7
4
2
8
GAME 8
1
1
1
1
2
2

output:

BNQRKBRN
RKBQNNRB
RNBBQNKR
RKRBQNBN
BBNNQRKR
RKQBBNNR
QRKNBBNR
BRKQRNNB
RBQNBNKR
RKNBBQNR
NBRKNQBR
RKRBBNQN
RKRNBNQB
RKNBBNQR
RBQKNNBR
RBQNKNBR
RKQBNNBR
NRQNKRBB
NQBBRKNR
RQNKNBBR
QRNKBBNR
BBNNQRKR
RKNBQNBR
RBBKNRQN
RKNBRQBN
RKNBBQRN
RKNBNQBR
NBQNBRKR
NRQNKRBB
RKQNBBNR
BNQRKBRN
RQBNNKRB
RNKBRNBQ
BBR...

result: