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

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: ロロット
• 提出日時: 2025-12-25 00:21:10
• 言語: C++17 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 83 ms / 5,000 ms
• コード長: 4,593 bytes
• コンパイル時間: 1,381 ms
• コンパイル使用メモリ: 105,248 KB
• 実行使用メモリ: 26,356 KB
• スコア: 9,992,363
• 平均クエリ数: 76.37
• 最終ジャッジ日時: 2025-12-25 00:25:46
• 合計ジャッジ時間: 14,055 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
other	AC * 100

ソースコード

// Solved by Gemini3.0
// 問題文を与えて全部任せました。インタラクティブのジャッジも書いてもらいました。
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

using namespace std;

// Function to calculate Hit and Blow
pair<int, int> get_hit_blow(const string& s, const string& q) {
    int h = 0;
    int b = 0;
    // s and q are guaranteed to be distinct digit strings of length 5
    // But let's be generic
    for (int i = 0; i < 5; ++i) {
        if (s[i] == q[i]) {
            h++;
        }
    }

    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            if (i == j) continue;
            if (s[i] == q[j]) {
                b++;
            }
        }
    }
    return {h, b};
}

bool has_distinct_digits(const string& s) {
    int mask = 0;
    for (char c : s) {
        int d = c - '0';
        if ((mask >> d) & 1) return false;
        mask |= (1 << d);
    }
    return true;
}

int main() {
    // Optimize I/O operations
    ios_base::sync_with_stdio(false);
    // cin.tie(NULL); // Do not untie, we need flush behavior?
    // Actually interactive problems usually require flush.
    // cin.tie(NULL) prevents automatic flush of cout before cin.
    // We strictly manually flush or use endl.

    vector<string> candidates;
    candidates.reserve(30240);

    for (int i = 0; i < 100000; ++i) {
        string s = to_string(i);
        while (s.length() < 5) s = "0" + s;
        if (has_distinct_digits(s)) {
            candidates.push_back(s);
        }
    }

    set<string> found_strings;
    // We need to find 30 strings.

    while (found_strings.size() < 30) {
        // Pick a query
        // We pick the first candidate that is not already found.
        // Actually, we can just remove candidates as we go.
        // But filtering creates a new vector anyway.

        string q;
        if (candidates.empty()) {
            // Should not happen if logic is correct and 30 strings exist
            break;
        }
        q = candidates[0];

        // Output query
        cout << q << endl;

        // Read response
        vector<pair<int, int>> response(30);
        int cnt_5_0 = 0;
        map<pair<int, int>, int> response_counts;

        for (int i = 0; i < 30; ++i) {
            cin >> response[i].first >> response[i].second;
            if (response[i] == make_pair(5, 0)) {
                cnt_5_0++;
            }
            response_counts[response[i]]++;
        }

        // Check if we found new strings
        // The number of (5, 0) tells us exactly how many found strings are there.
        // If q was not in found_strings, and now we have more (5,0)s, q is found.
        // Wait, 'cnt_5_0' is the TOTAL number of identified strings.

        // Check if q is a newly found string
        bool q_is_found = false;
        if (cnt_5_0 > (int)found_strings.size()) {
            // Since we only query one string q at a time,
            // the count can increase by at most 1 (if q is a new hidden string).
            // It matches q.
            found_strings.insert(q);
            q_is_found = true;
        }

        if (found_strings.size() == 30) {
            break;
        }

        // Prepare the multiset of responses for the UNKNOWN candidates.
        // We remove 'cnt_5_0' counts of (5, 0) from the response_counts.
        // Because those correspond to the found strings (including q if it was found).
        if (response_counts.count({5, 0})) {
            response_counts[{5, 0}] -= cnt_5_0;
            if (response_counts[{5, 0}] <= 0) {
                response_counts.erase({5, 0});
            }
        }

        // Filter candidates
        vector<string> next_candidates;
        next_candidates.reserve(candidates.size());

        for (const string& c : candidates) {
            // If c is already found, we don't need to keep it in candidates
            // (Unless we want to be explicit, but it's better to remove to shrink search space)
            if (found_strings.count(c)) continue;

            // If c == q and q was NOT found, then c is definitely not a hidden string.
            // (If q was found, we already skipped it above).
            if (c == q) continue;

            pair<int, int> hb = get_hit_blow(c, q);

            // Check if hb is in the remaining response counts
            if (response_counts.count(hb)) {
                next_candidates.push_back(c);
            }
        }

        candidates = next_candidates;
    }

    return 0;
}