結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー FplusFplusF
提出日時 2025-12-30 00:46:24
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 375 ms / 5,000 ms
コード長 8,796 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,610 ms
コンパイル使用メモリ 307,652 KB
実行使用メモリ 37,220 KB
スコア 9,995,366
平均クエリ数 46.34
最終ジャッジ日時 2025-12-30 00:47:14
合計ジャッジ時間 40,600 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
using qii=tuple<int,int,int,int>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
constexpr int INF=1e9;
constexpr ll INF_ll=1e18;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((int)v.size())
template<class T> inline bool chmin(T &a,T b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

namespace Timer{
    chrono::system_clock::time_point program_start,start;
    void program_start_snap(){
        program_start=start=chrono::system_clock::now();
    }
    void snap(){
        start=chrono::system_clock::now();
    }
    int get_ms(){
        auto now=chrono::system_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
        return ms;
    }
    int get_ms_all_program(){
        auto now=chrono::system_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-program_start).count();
        return ms;
    }
}

mt19937 mt;
uint32_t rand_int(uint32_t r){  //[0,r)
    assert(r!=0);
    return ((uint64_t)mt()*r)>>32;
}
int rand_int(int l,int r){  //[l,r)
    assert(l<r);
    return l+rand_int(r-l);
}
constexpr double one_div_mt_max=1.0/(double)mt19937::max();
double rand_double(){  //[0.0,1.0]
    return mt()*one_div_mt_max;
}

template<class T> T get_random_element(const vector<T> &v){
    assert(!v.empty());
    return v[rand_int(len(v))];
}

template<class T> void add(vector<T> &a,vector<T> b){
    for(auto i:b) a.push_back(i);
}

constexpr int N=30,K=5,SZ=30240;

vector<string> C;

int get_hb(int x_idx,int y_idx){  //TODOかも
    
    const string &x=C[x_idx];
    const string &y=C[y_idx];
    
    int h=0,b=0;
    
    rep(k,K){
        if(x[k]==y[k]) h++;
    }
    rep(k,K){
        rep(l,K){
            if(k==l) continue;
            if(x[k]==y[l]) b++;
        }
    }
    
    return h*6+b;
}


namespace Communication{
    
    vector<string> S;
    
    vector<int> finished;
    
    void init(){
        S.resize(N);
        finished.resize(N,false);
        
        auto c=C;
        
        shuffle(all(c),mt);
        
        rep(i,N){
            S[i]=c[i];
            
            cerr << "ans:" << S[i] << '\n';
        }
        
        cerr << '\n';
    }
    
    int turn=0,finished_cnt=0;
    
    vector<pii> query(int q_idx){
        
        string q=C[q_idx];
        
        turn++;
        
        assert(len(q)==K);
        
        vector<pii> ret(N);
        
        #ifdef LOCAL
        
        rep(i,N){
            
            if(S[i]==q||finished[i]){
                ret[i]={5,0};
                if(!finished[i]) finished_cnt++;
                finished[i]=true;
                continue;
            }
            
            int h=0,b=0;
            rep(k,K){
                if(S[i][k]==q[k]) h++;
            }
            rep(k,K){
                rep(l,K){
                    if(k==l) continue;
                    if(S[i][k]==q[l]) b++;
                }
            }
            ret[i]={h,b};
        }
        sort(all(ret));
        
        #else
        
        cout << q << '\n';
        cout.flush();
        
        finished_cnt=0;
        
        rep(i,N){
            int h,b;
            cin >> h >> b;
            if(h==K&&b==0) finished_cnt++;
            ret[i]={h,b};
        }
        
        #endif
        
        
        
        if(ret.front()==pii{K,0}){
            cerr << "turn:" << turn << '\n';
            exit(0);
        }
        
        if(ret.front()==pii{-1,-1}) assert(0);
        
        
        return ret;
    }
};

struct History{
    int q;
    int hb;
    vector<int> idxs;
    int now_cnt,true_cnt;
};

namespace Solver{
    
    vector<History> historys;
    
    void solve(){
        
        vector<int> is_s(SZ,-1);  //-1:不明 0:No 1:Yes
        
        vector<int> accepting_idx,accepted_idx;
        
        int pre_ac=0;
        
        vector<vector<int>> idx_history(SZ);  //[i]=set_cnt_historysに入っているインデックスの集合
        
        while(true){
            
            int q_idx=-1;
            
            if(!accepting_idx.empty()){
                
                q_idx=accepting_idx.back();
                accepting_idx.pop_back();    
                
            }else{
                
                double best_score=-INF;
                
                rep(i,SZ){
                    
                    if(is_s[i]!=-1) continue;
                    
                    double score=0;
                    for(auto j:idx_history[i]){
                        const auto &[q,hb,idxs,now_cnt,true_cnt]=historys[j];
                        if(now_cnt!=true_cnt){
                            score+=(double)(true_cnt-now_cnt)/(double)(len(idxs)-now_cnt);
                        }
                    }
                    
                    if(chmax(best_score,score)) q_idx=i;
                }
            }
            
            if(q_idx==-1) break;
            
            
            vector<pii> hbs=Communication::query(q_idx);
            
            vector<int> hb_cnt(36,0);
            
            int now_ac=0;
            
            for(auto [h,b]:hbs){
                if(h==K){
                    now_ac++;
                    continue;
                }
                hb_cnt[h*6+b]++;
            }
            
            if(pre_ac!=now_ac){
                
                cerr << "ok:" << C[q_idx] << endl;
                
                is_s[q_idx]=1;
                accepted_idx.push_back(q_idx);
            }else{
                is_s[q_idx]=0;
            }
            
            pre_ac=now_ac;
            
            for(auto i:accepted_idx){
                hb_cnt[get_hb(q_idx,i)]++;
            }
            
            
            vector<int> new_c;
            
            vector<vector<int>> hb_set(36);
            
            rep(i,SZ){
                int hb=get_hb(q_idx,i);
                hb_set[hb].push_back(i);
            }
            
            rep(hb,36){
                
                for(auto i:hb_set[hb]){
                    idx_history[i].push_back(len(historys));
                }
                
                historys.emplace_back(q_idx,hb,hb_set[hb],0,hb_cnt[hb]);
            }
            
            while(true){
                
                bool finish=true;
            
                for(auto &[q,hb,idxs,now_cnt,true_cnt]:historys){
                    
                    //if(true_cnt==now_cnt) continue;
                    
                    int in_cnt=0,unknown_cnt=0;
                    
                    for(auto i:idxs){
                        if(is_s[i]==-1) unknown_cnt++;
                        if(is_s[i]==1) in_cnt++;
                    }
                    
                    
                    assert(in_cnt<=true_cnt);
                    
                    if(in_cnt==true_cnt){
                        
                        for(auto i:idxs){
                            if(is_s[i]==-1){
                                is_s[i]=0;
                                finish=false;
                            }
                        }
                        
                        
                    }else if(true_cnt-in_cnt==unknown_cnt){
                        
                        for(auto i:idxs){
                            if(is_s[i]==-1){
                                
                                cerr << "ok2:" << C[i] << endl;
                                
                                is_s[i]=1;
                                accepting_idx.push_back(i);
                                finish=false;
                            }
                        }
                    }
                    
                    now_cnt=in_cnt;
                }
                
                if(finish) break;
            }
        }
        
        assert(0);
        
    }
}

void init(){
    rep(i,100000){
        string s=to_string(i);
        while(len(s)<K) s.insert(s.begin(),'0');
        string t=s;
        sort(all(t));
        t.erase(unique(all(t)),t.end());
        if(len(t)==K){
            C.push_back(s);
        }
    }
    
    assert(len(C)==SZ);
    
    #ifdef LOCAL
    
    Communication::init();
    
    #endif
}

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



    Solver::solve();
    exit(0);
}
0