結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー FplusFplusF
提出日時 2025-12-25 01:18:55
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
RE  
実行時間 -
コード長 6,666 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,587 ms
コンパイル使用メモリ 316,644 KB
実行使用メモリ 26,260 KB
スコア 4,183,555
平均クエリ数 17704.23
最終ジャッジ日時 2025-12-25 01:27:32
合計ジャッジ時間 122,199 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42 RE * 58
権限があれば一括ダウンロードができます

ソースコード

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_same_group(string first_s){
        
        vector<string> all_c;
        
        do{
            
            all_c.push_back(first_s);
            
        }while(next_permutation(all(first_s)));
        
        auto c=all_c;
        
        
        while(true){
            
            string best_str;
            
            int best_mx=INF;
            
            
            if(len(c)==1){
                
                best_str=c.front();
                
            }else{
            
                for(const auto &x:all_c){
                    map<pii,int> mp;
                    for(const auto &y:c){
                        mp[get_hb(x,y)]++;
                    }
                    
                    int mx=0;
                    for(auto [_,cnt]:mp){
                        chmax(mx,cnt);
                    }
                    
                    if(chmin(best_mx,mx)){
                        best_str=x;
                    }
                }
                
            }
            
            int pre_finished_cnt=Communication::finished_cnt;
            
            auto hb=Communication::query(best_str);
            
            int nh=-1,nb=-1;
            
            for(auto [h,b]:hb){
                if(h!=K&&h+b==K){
                    nh=h;
                    nb=b;
                }
            }
            if(pre_finished_cnt<Communication::finished_cnt) break;
            
            vector<string> new_c;
            
            for(const auto &y:c){
                //auto [h,b]=get_hb(best_str,y);
                if(pii{nh,nb}==get_hb(best_str,y)) new_c.push_back(y);
            }
            
            
            c=new_c;
        }
        
        
    }
    
    void solve(){
        
        auto c=C;
        
        for(auto &i:c){
            sort(all(i));
        }
        
        sort(all(c));
        c.erase(unique(all(c)),c.end());
        
        
        rep(idx,len(c)){
            
            
            vector<pii> hb=Communication::query(c[idx]);
            
            
            
            int in_cnt=0;
            
            for(auto [h,b]:hb){
                if(h!=K&&h+b==K) in_cnt++;
            }
            
            
            rep(_,in_cnt) solve_same_group(c[idx]);
        }
        
        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