結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー FplusFplusF
提出日時 2025-12-25 01:53:05
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 101 ms / 5,000 ms
コード長 4,976 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,468 ms
コンパイル使用メモリ 305,612 KB
実行使用メモリ 26,216 KB
スコア 9,986,244
平均クエリ数 137.56
最終ジャッジ日時 2025-12-25 01:57:12
合計ジャッジ時間 15,149 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;

vector<string> C;

pii get_hb(const string &x,const string &y){  //TODO
    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,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(string q){
        
        turn++;
        
        assert(len(q)==K);
        
        cout << q << '\n';
        cout.flush();
        
        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
        
        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;
    }
};

namespace Solver{
    
    void solve(){
        
        auto c=C;
        
        rep(_,100){
            
            string str=get_random_element(C);
            
            
            
            vector<pii> hb=Communication::query(str);
            
            set<pii> st(all(hb));
            
            vector<string> new_c;
            
            for(const auto &x:c){
                
                if(st.contains(get_hb(str,x))){
                    new_c.push_back(x);
                }
            }
            
            
            c=new_c;
        }
        
        for(auto str:c){
            Communication::query(str);
        }
        
        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);
        }
    }
    
    #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