結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー syndrome
提出日時 2025-12-25 01:22:31
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 69 ms / 5,000 ms
コード長 4,340 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,153 ms
コンパイル使用メモリ 334,884 KB
実行使用メモリ 25,972 KB
スコア 9,995,244
平均クエリ数 47.56
最終ジャッジ日時 2025-12-25 01:28:11
合計ジャッジ時間 14,572 ms
ジャッジサーバーID
（参考情報） 		judge2 / 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;}

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;
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, 11) 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);
    // InitBot();
    vc<double> prb(cnt, N / (double)cnt);
    int score = 0;
    int FIND = 0;
    while (FIND < N){
        score++;
        int q;
        double best = 0;
        rep(i, cnt) if (best < prb[i]){
            q = i;
            best = prb[i];
        }
        cout << cand[q] << endl;
        // auto ret = LocalBot(cand[q]);
        vc<pair<int, int>> ret;
        rep(i, N){
            int h, b; cin >> h >> b;
            ret.push_back({h, b});
        }
        if (ret[0] == make_pair(5, 0)) break;
        vvi P(6, vi(6, 0));
        for (auto [h, b] : ret){
            P[h][b]++;
        }
        vvvi rt(6, vvi(6));
        rep(i, cnt) if (prb[i] > 0){
            auto [h, b] = hb(cand[q], cand[i]);
            if (h == 5){
                prb[i] = 0;
            }else{
                rt[h][b].push_back(i);
            }
        }

        rep(h, 6) rep(b, 6) if (len(rt[h][b])){
            double sm = 0;
            for (auto i : rt[h][b]) sm += prb[i];
            double coeff = P[h][b] / sm;
            for (auto i : rt[h][b]) prb[i] *= coeff;
        }
    }
    cerr << score << endl;
}
0