#1140379 (C++23) No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: butsurizuki
• 提出日時: 2025-12-14 22:12:19
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 11,683 bytes
• コンパイル時間: 4,711 ms
• コンパイル使用メモリ: 327,580 KB
• 実行使用メモリ: 26,616 KB
• スコア: 5,496,427
• 平均クエリ数: 35.08
• 最終ジャッジ日時: 2025-12-25 01:40:57
• 合計ジャッジ時間: 24,082 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
other	AC * 55 TLE * 1 -- * 44

ソースコード

// by GPT 5.2 Pro 2nd attempt
#include <bits/stdc++.h>
using namespace std;

static constexpr int L = 5;
static constexpr int DIG = 10;
static constexpr int BUCKET = 36;          // (H,B) -> H*6 + B
static constexpr int IDX_50 = 5 * 6 + 0;   // (5,0) bucket = 30

struct Code {
    array<char, L> d;
    uint16_t mask;     // 10-bit
    string s;
};

struct FoundInfo {
    int codeIdx;       // index in all codes
    int discoveredAt;  // query index when it first became (5,0)
};

struct AskResult {
    array<int, BUCKET> hist{};
    int firstH = -1, firstB = -1; // (H0,B0)
    int count50 = 0;              // # of (5,0)
    bool invalid = false;         // (-1,-1) seen
};

static inline int popcount16(uint16_t x) {
    return __builtin_popcount((unsigned)x);
}

static inline int hb_bucket(const Code &c, const array<char,L> &qDig, uint16_t qMask) {
    int h = 0;
    for (int i = 0; i < L; i++) if (c.d[i] == qDig[i]) h++;
    int common = popcount16(uint16_t(c.mask & qMask));
    int b = common - h;
    return h * 6 + b;
}

static inline pair<array<char,L>, uint16_t> parse_query(const string &q) {
    array<char,L> qd{};
    uint16_t m = 0;
    for (int i = 0; i < L; i++) {
        qd[i] = q[i];
        m |= uint16_t(1u << (q[i] - '0'));
    }
    return {qd, m};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // --- Enumerate all 30240 codes ---
    vector<Code> codes;
    codes.reserve(30240);
    unordered_map<string,int> codeId;
    codeId.reserve(40000);

    for (int a = 0; a < 10; a++) for (int b = 0; b < 10; b++) if (b != a)
    for (int c = 0; c < 10; c++) if (c != a && c != b)
    for (int d = 0; d < 10; d++) if (d != a && d != b && d != c)
    for (int e = 0; e < 10; e++) if (e != a && e != b && e != c && e != d) {
        Code x;
        x.d = {char('0'+a), char('0'+b), char('0'+c), char('0'+d), char('0'+e)};
        x.mask = uint16_t((1u<<a)|(1u<<b)|(1u<<c)|(1u<<d)|(1u<<e));
        x.s = string{x.d.begin(), x.d.end()};
        int idx = (int)codes.size();
        codes.push_back(x);
        codeId.emplace(x.s, idx);
    }
    const int N = (int)codes.size();

    // --- State ---
    vector<string> askedQueries;                 // query strings (in order)
    vector<array<int, BUCKET>> histByQuery;      // histogram per query
    vector<vector<uint8_t>> bucketByQuery;       // bucketByQuery[qIndex][codeIndex]
    vector<FoundInfo> found;                     // discovered secrets
    vector<char> isFound(N, 0), isBlocked(N, 0); // blocked = asked and not secret

    unordered_set<string> askedSet;
    askedSet.reserve(2000);

    auto ask = [&](const string &q) -> AskResult {
        // output query
        cout << q << "\n" << flush;

        AskResult res;
        res.hist.fill(0);
        res.count50 = 0;
        res.invalid = false;

        for (int i = 0; i < 30; i++) {
            int h, b;
            if (!(cin >> h >> b)) {
                // EOF or input error -> just exit
                exit(0);
            }
            if (i == 0) { res.firstH = h; res.firstB = b; }
            if (h == -1 && b == -1) res.invalid = true;
            if (!res.invalid) {
                int idx = h * 6 + b;
                if (0 <= idx && idx < BUCKET) res.hist[idx]++;
                if (h == 5 && b == 0) res.count50++;
            }
        }

        if (res.invalid) exit(0);
        if (res.firstH == 5 && res.firstB == 0) exit(0); // solved, must terminate

        return res;
    };

    auto add_query_row = [&](const string &q) {
        auto [qDig, qMask] = parse_query(q);
        vector<uint8_t> row(N);
        for (int i = 0; i < N; i++) {
            int b = hb_bucket(codes[i], qDig, qMask);
            row[i] = (uint8_t)b;
        }
        bucketByQuery.push_back(std::move(row));
    };

    auto register_if_new_secret = [&](const string &q, int queryIndex, int count50) {
        // count50 is total number of (5,0) returned by judge this turn
        // if it increased by 1, q must be a newly found secret (since all S_i are distinct)
        int prevFound = (int)found.size();
        if (count50 == prevFound + 1) {
            int idx = codeId[q];
            if (!isFound[idx]) {
                isFound[idx] = 1;
                found.push_back({idx, queryIndex});
            }
        }
    };

    auto build_need_counts = [&]() {
        int Q = (int)histByQuery.size();
        vector<array<int, BUCKET>> need = histByQuery; // copy
        for (const auto &f : found) {
            for (int j = 0; j < Q; j++) {
                if (j >= f.discoveredAt) {
                    need[j][IDX_50]--;
                } else {
                    int b = bucketByQuery[j][f.codeIdx];
                    need[j][b]--;
                }
            }
        }
        return need;
    };

    auto build_pool = [&](const vector<array<int, BUCKET>> &need) {
        int Q = (int)need.size();
        int remain = 30 - (int)found.size();
        (void)remain;

        vector<int> pool;
        pool.reserve(N);
        for (int i = 0; i < N; i++) {
            if (isFound[i] || isBlocked[i]) continue;
            bool ok = true;
            for (int j = 0; j < Q; j++) {
                int b = bucketByQuery[j][i];
                if (need[j][b] == 0) { ok = false; break; }
            }
            if (ok) pool.push_back(i);
        }
        return pool;
    };

    // DFS reconstruction: find exactly "remain" codes that match all histograms
    auto reconstruct = [&](vector<int> &out) -> bool {
        int Q = (int)histByQuery.size();
        int remain = 30 - (int)found.size();
        if (remain == 0) { out.clear(); return true; }
        if (Q == 0) return false;

        auto need = build_need_counts();
        auto pool = build_pool(need);

        // too large -> not ready, add more probes
        if ((int)pool.size() > 2500) return false;

        if ((int)pool.size() == remain) {
            out = pool;
            return true;
        }
        if ((int)pool.size() < remain) return false;

        // bucketCodes[q][bucket] = list of codes in pool with that bucket in query q
        vector<vector<vector<int>>> bucketCodes(Q, vector<vector<int>>(BUCKET));
        for (int idx : pool) {
            for (int j = 0; j < Q; j++) {
                bucketCodes[j][ bucketByQuery[j][idx] ].push_back(idx);
            }
        }

        vector<int> sol;
        sol.reserve(remain);
        vector<char> used(N, 0);

        auto start = chrono::steady_clock::now();
        long long nodes = 0;

        function<bool(int)> dfs = [&](int depth) -> bool {
            if (depth == remain) {
                for (int j = 0; j < Q; j++)
                    for (int b = 0; b < BUCKET; b++)
                        if (need[j][b] != 0) return false;
                return true;
            }

            // time guard (about 1.2s for reconstruction)
            if ((nodes++ & 2047) == 0) {
                double sec = chrono::duration<double>(chrono::steady_clock::now() - start).count();
                if (sec > 1.2) return false;
            }

            int bestJ = -1, bestB = -1;
            int bestSize = INT_MAX;

            for (int j = 0; j < Q; j++) {
                for (int b = 0; b < BUCKET; b++) {
                    if (need[j][b] > 0) {
                        int sz = (int)bucketCodes[j][b].size();
                        if (sz < bestSize) {
                            bestSize = sz;
                            bestJ = j;
                            bestB = b;
                        }
                    }
                }
            }
            if (bestJ < 0) return false;

            auto &cand = bucketCodes[bestJ][bestB];

            for (int idx : cand) {
                if (used[idx]) continue;

                bool ok = true;
                for (int j = 0; j < Q; j++) {
                    int b = bucketByQuery[j][idx];
                    if (need[j][b] == 0) { ok = false; break; }
                }
                if (!ok) continue;

                used[idx] = 1;
                sol.push_back(idx);
                for (int j = 0; j < Q; j++) {
                    need[j][ bucketByQuery[j][idx] ]--;
                }

                if (dfs(depth + 1)) return true;

                for (int j = 0; j < Q; j++) {
                    need[j][ bucketByQuery[j][idx] ]++;
                }
                sol.pop_back();
                used[idx] = 0;
            }

            return false;
        };

        if (dfs(0)) {
            out = sol;
            return true;
        }
        return false;
    };

    // Random probe generator (deterministic seed)
    mt19937 rng(1234567);

    auto random_query = [&]() -> string {
        array<int, DIG> v{};
        iota(v.begin(), v.end(), 0);
        shuffle(v.begin(), v.end(), rng);
        string q;
        q.reserve(L);
        for (int i = 0; i < L; i++) q.push_back(char('0' + v[i]));
        return q;
    };

    int probeTarget = 35;
    int probeMax = 60;

    while ((int)found.size() < 30) {
        // --- probe phase (add until target) ---
        while ((int)askedQueries.size() < probeTarget && (int)found.size() < 30) {
            string q;
            do {
                q = random_query();
            } while (askedSet.count(q));
            askedSet.insert(q);

            AskResult ar = ask(q);

            int qIndex = (int)askedQueries.size();
            askedQueries.push_back(q);
            histByQuery.push_back(ar.hist);
            add_query_row(q);

            register_if_new_secret(q, qIndex, ar.count50);
        }
        if ((int)found.size() >= 30) break;

        // --- try reconstruction ---
        vector<int> predicted;
        bool ok = reconstruct(predicted);

        if (ok) {
            // query predicted secrets
            for (int idx : predicted) {
                if ((int)found.size() >= 30) break;
                if (isFound[idx] || isBlocked[idx]) continue;

                string q = codes[idx].s;
                if (askedSet.count(q)) continue; // avoid repeats
                askedSet.insert(q);

                AskResult ar = ask(q);

                int qIndex = (int)askedQueries.size();
                askedQueries.push_back(q);
                histByQuery.push_back(ar.hist);
                add_query_row(q);

                int prevFound = (int)found.size();
                register_if_new_secret(q, qIndex, ar.count50);
                if ((int)found.size() == prevFound) {
                    // not a secret
                    isBlocked[idx] = 1;
                }
            }
        }

        if ((int)found.size() >= 30) break;

        // --- if still not solved, add more probes or fallback ---
        if (probeTarget < probeMax) {
            probeTarget += 5;
            continue;
        }

        // Fallback: brute-force only within current pool (much smaller than 30240)
        auto need = build_need_counts();
        auto pool = build_pool(need);
        for (int idx : pool) {
            if ((int)found.size() >= 30) break;
            if (isFound[idx] || isBlocked[idx]) continue;

            string q = codes[idx].s;
            if (askedSet.count(q)) continue;
            askedSet.insert(q);

            AskResult ar = ask(q);

            int qIndex = (int)askedQueries.size();
            askedQueries.push_back(q);
            histByQuery.push_back(ar.hist);
            add_query_row(q);

            int prevFound = (int)found.size();
            register_if_new_secret(q, qIndex, ar.count50);
            if ((int)found.size() == prevFound) isBlocked[idx] = 1;
        }
    }

    return 0;
}