結果

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

ソースコード

diff #
raw source code 

// (◕ᴗ◕✿)

// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define srep(i, s, n) for (ll i = s; i < (n); i++)
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
template<typename T> using vvv = vv<vc<T>>;
using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>;
using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>;
using uint = unsigned int;
using ull = unsigned long long;
const ld pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
// const ll mod = 1000000007;
const ll mod = 998244353;
inline bool inside(ll y, ll x, ll H, ll W) {return 0 <= (y) and (y) < (H) and 0 <= (x) and (x) < (W); }

#define debug(var) do { cerr << #var << " :\n"; view(var); } while(0)
template<typename T>void view(const T& e) {cerr << e;}
template<typename T1, typename T2>void view(const pair<T1, T2>& p) {cerr << "{" << p.first << ", " << p.second << "}";}
template<typename T>void view(const vc<T>& v) {for (const auto& e : v) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const vv<T>& vv) {for (const auto& v : vv) {view(v);} cerr << endl;}
template<typename T>void view(const set<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const multiset<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const unordered_set<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T1, typename T2>void view(const map<T1, T2>& mp){for (const auto& e : mp) {view(e);cerr << " ";} cerr << endl;}
// #define DEBUG

#ifdef DEBUG
constexpr bool DEBUGMODE = true;
#else
constexpr bool DEBUGMODE = false;
#endif

unsigned int randxor(){
    static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned int t;
    t = (x ^ (x << 11)); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
int randint(int a, int b) {return(a + randxor() % (b - a));}

constexpr int N = 30;
constexpr int MAXSCORE = 100;
vc<string> cand;
int cnt;
set<string> answer;

pair<int, int> hb(string q, string p){
    int h = 0, b = 0;
    vi F(10, 0);
    rep(i, 5) F[p[i] - '0'] = 1;
    rep(i, 5) if (q[i] == p[i]) h++;
    rep(i, 5) b += F[q[i] - '0'];
    b -= h;
    return {h, b};
}

void InitBot(){
    while (len(answer) < N){
        int i = randint(0, cnt);
        answer.insert(cand[i]);
    }
}

vc<pair<int, int>> LocalBot(string a){
    vc<pair<int, int>> ret;
    rep(i, N - len(answer)) ret.push_back({5, 0});
    for (auto x : answer){
        auto [h, b] = hb(a, x);
        ret.push_back({h, b});
    }
    if (answer.count(a)) answer.erase(a);
    sort(all(ret));
    return ret;
}

int main(){
    // rep(i, 2) randxor();
    rep(i, 100000){
        string a = to_string(i);
        while (len(a) < 5) a = "0" + a;
        bool ok = true;
        rep(y, 5) rep(x, y) if (a[x] == a[y]){
            ok = false;
        }
        if (ok) cand.push_back(a);
    }
    cnt = len(cand);
    if (DEBUGMODE) InitBot();
    vc<double> prb(cnt, N / (double)cnt);
    int score = 0;
    int FIND = 0;
    array<string, MAXSCORE> Q;
    array<array<array<int, 6>, 6>, MAXSCORE> P;
    array<array<array<vi, 6>, 6>, MAXSCORE> rt;
    rep(i, MAXSCORE) rep(j, 6) rep(k, 6) P[i][j][k] = 0;

    auto update_prb = [&](int id) -> void {
        rep(h, 6) rep(b, 6) if (len(rt[id][h][b])){
            double sm = 0;
            for (auto i : rt[id][h][b]) sm += prb[i];
            if (sm < 1e-13) continue;
            double coeff = P[id][h][b] / sm;
            for (auto i : rt[id][h][b]) prb[i] *= coeff;
        }
    };

    while (true){
        int q;
        double best = 0;
        rep(i, cnt) if (best < prb[i]){
            q = i;
            best = prb[i];
        }
        vc<pair<int, int>> ret;
        if (DEBUGMODE){
            ret = LocalBot(cand[q]);
        }else{
            cout << cand[q] << endl;
            rep(i, N){
                int h, b; cin >> h >> b;
                ret.push_back({h, b});
            }
        }
        Q[score] = cand[q];
        if (ret[0] == make_pair(5, 0)) break;
        for (auto [h, b] : ret){
            P[score][h][b]++;
        }
        if (ret[N - FIND - 1] == make_pair(5, 0)){
            rep(j, score){
                auto [nh, nb] = hb(Q[j], Q[score]);
                P[j][nh][nb]--;
            }
            FIND++;
        }
        rep(i, cnt) if (prb[i] > 0){
            auto [h, b] = hb(cand[q], cand[i]);
            if (h == 5){
                prb[i] = 0;
            }else{
                rt[score][h][b].push_back(i);
            }
        }

        update_prb(score);
        rep(j, 5) rep(i, score + 1) update_prb(i);
        // if (score == 20) debug(prb);

        score++;
    }
    cerr << score + 1 << endl;
}
0