結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー 👑 wanui
提出日時 2025-12-25 01:16:33
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 85 ms / 5,000 ms
コード長 6,822 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,852 ms
コンパイル使用メモリ 230,388 KB
実行使用メモリ 25,972 KB
スコア 9,954,391
平均クエリ数 456.09
最終ジャッジ日時 2025-12-25 01:17:57
合計ジャッジ時間 12,958 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
// clang-format off
using namespace std;
#define debug1(a) { cerr<<#a<<":"<<a<<endl; }
#define debug2(a,b) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; }
#define debug3(a,b,c) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; }
#define debug4(a,b,c,d) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; }
// clang-format on
using pii = pair<int, int>;
const int L = 5;
const int N = 30;
const int D = 10;
const int LOCAL = 0;
namespace Judge {

class Judge {
   public:
    vector<vector<int>> local_ans;
    vector<int> success;
    vector<pair<vector<int>, vector<pii>>> history;
    void initialize_ans() {
        if (!LOCAL) return;
        std::random_device seed_gen;
        mt19937 engine;
        engine.seed(seed_gen());

        local_ans.clear();
        for (int i = 0; i < N; i++) {
            while (true) {
                vector<int> ten(10);
                iota(ten.begin(), ten.end(), 0);
                shuffle(ten.begin(), ten.end(), engine);
                vector<int> five(5);
                for (int k = 0; k < 5; k++) {
                    five[k] = ten[k];
                }
                bool ok = true;
                for (auto e : local_ans) {
                    if (e == five) ok = false;
                }
                if (ok) {
                    local_ans.push_back(five);
                    break;
                }
            }
        }
        success = vector<int>(N);
    }
    vector<pii> request(vector<int> q) {
        for (int k = 0; k < 5; k++) {
            cout << q[k];
        }
        cout << endl;

        vector<pii> res(N);
        if (LOCAL) {
            for (int i = 0; i < N; i++) {
                if (success[i]) {
                    res[i] = {5, 0};
                    continue;
                }
                int h = 0;
                int b = 0;
                for (int k = 0; k < 5; k++) {
                    for (int l = 0; l < 5; l++) {
                        if (q[k] == local_ans[i][l]) {
                            if (k == l) {
                                h++;
                            } else {
                                b++;
                            }
                        }
                    }
                }
                res[i] = {h, b};
                if (res[i] == pii{5, 0}) {
                    success[i] = 1;
                }
            }
            sort(res.begin(), res.end());
        } else {
            for (int i = 0; i < N; i++) {
                cin >> res[i].first >> res[i].second;
            }
        }
        history.push_back({q, res});
        return res;
    }
};
}  // namespace Judge

class Solver {
   public:
    vector<vector<int>> get_candidate() {
        auto check = [](string s) {
            sort(s.begin(), s.end());
            for (int i = 1; i < s.size(); i++) {
                if (s[i - 1] == s[i]) {
                    return false;
                }
            }
            return true;
        };
        vector<string> s;
        for (int i = 0; i <= 99999; i++) {
            int v = i;
            string cur;
            for (int j = 0; j < 5; j++) {
                cur.push_back('0' + v % 10);
                v /= 10;
            }
            reverse(cur.begin(), cur.end());
            if (check(cur)) {
                s.push_back(cur);
            }
        }
        vector<vector<int>> res;
        for (auto &nx : s) {
            vector<int> q = {nx[0] - '0', nx[1] - '0', nx[2] - '0', nx[3] - '0', nx[4] - '0'};
            res.push_back(q);
        }
        return res;
    }
    void solve() {
        mt19937 engine;
        {
            std::random_device seed_gen;
            engine.seed(seed_gen());
        }

        auto judge = Judge::Judge();
        judge.initialize_ans();

        // vector<vector<int>> candidate = get_candidate();
        set<vector<int>> checked;

        int success = 0;

        tuple<int, pii, vector<int>> prev = {-1, {-1, -1}, {0, 1, 2, 3, 4}};
        set<int> bad_k;

        while (true) {
            debug2(success, judge.history.size());
            int change_k = -1;
            pii swaps = {-1, -1};
            vector<int> q;
            for (int it = 0; it < 10000; it++) {
                q = get<2>(prev);
                if (!judge.history.size()) break;

                auto best_match = get<1>(prev);
                if (it >= 100 || bad_k.size() >= 5) {
                    bad_k = set<int>();
                    vector<int> ten(10);
                    iota(ten.begin(), ten.end(), 0);
                    shuffle(ten.begin(), ten.end(), engine);
                    vector<int> five(5);
                    for (int k = 0; k < 5; k++) {
                        five[k] = ten[k];
                    }
                    q = five;
                } else if (best_match.first + best_match.second == L) {
                    int si = 0;
                    int sj = 0;
                    while (si == sj) {
                        si = engine() % L;
                        sj = engine() % L;
                    }
                    swaps = {si, sj};
                    swap(q[si], q[sj]);
                } else {
                    int k = engine() % L;
                    while (bad_k.count(k)) {
                        k = engine() % L;
                    }
                    change_k = k;
                    int d = engine() % D;
                    q[k] = d;
                }
                if (checked.count(q)) continue;
                set<int> qs;
                for (auto e : q) qs.insert(e);
                if (qs.size() != 5) continue;
                break;
            }
            checked.insert(q);
            auto res = judge.request(q);

            int now_success = 0;
            pair<int, pii> best = {-1, {-1, -1}};
            for (int i = 0; i < N; i++) {
                int h, b;
                tie(h, b) = res[i];
                if (h == 5) {
                    now_success++;
                } else {
                    int f = h * 10 + b * 9;  // TODO
                    best = max(best, {f, {h, b}});
                }
            }
            if (now_success == N) {
                debug1(judge.history.size());
                return;
            }
            assert(success <= now_success);
            if (success < now_success) {
                bad_k = set<int>();
            }
            if (success < now_success || best.first >= get<0>(prev)) {
                prev = {best.first, best.second, q};
            } else {
                if (change_k >= 0) {
                    bad_k.insert(change_k);
                }
            }
            success = now_success;
        }
    }
};
int main() {
    Solver().solve();
    return 0;
}
0