結果

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

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#include <sys/time.h>

using namespace std;

long long start_time;

void start_clock(){
  struct timeval tv;
  gettimeofday(&tv, NULL);
  start_time=(tv.tv_sec*1000000+tv.tv_usec);
}

long long current_clock(){
  struct timeval tv;
  gettimeofday(&tv, NULL);
  long long current_time=(tv.tv_sec*1000000+tv.tv_usec);
  // cout << current_time-start_time << "(us)\n";
  return current_time-start_time;
}

bool check(string s){
  sort(s.begin(),s.end());
  for(int i=1;i<s.size();i++){
    if(s[i-1]==s[i]){return false;}
  }
  return true;
}

using pi=pair<int,int>;

vector<int> ask(string s){
  cout << s << "\n";
  fflush(stdout);
  vector<pi> res(30);
  vector<int> rv;
  for(int i=0;i<30;i++){
    cin >> res[i].first >> res[i].second;
    rv.push_back(res[i].first*6+res[i].second);
  }
  // cerr << "done\n";
  if(res[0].first==5 || res[0].first<0){exit(0);} // finish
  return rv;
}

int hbc(string s,string t){
  int res=0;
  for(int k=0;k<5;k++){
    if(s[k]==t[k]){res+=6;}
  }
  for(int k=0;k<5;k++){
    for(int l=0;l<5;l++){
      if(k==l){continue;}
      if(s[k]==t[l]){res++;}
    }
  }
  return res;
}

vector<string> slis;
map<string,int> sinv;

vector<vector<int>> eqs;
vector<int> eqv; 
vector<vector<int>> einv;

vector<int> alive;

const double alpha=0.06;
vector<double> prob;

void run(){
  vector<double> gap(eqv.size());
  for(int i=0;i<eqv.size();i++){
    gap[i]=(-eqv[i]);
  }
  for(int i=0;i<eqv.size();i++){
    for(auto &nx : eqs[i]){
      gap[i]+=prob[nx];
    }
  }
  for(auto &nx : gap){ nx*=alpha; }
  for(int i=0;i<eqv.size();i++){
    if(eqs[i].size()==0){continue;}
    gap[i]/=((double)eqs[i].size());
    for(auto &nx : eqs[i]){
      prob[nx]-=gap[i];
    }
  }
  for(auto &nx : prob){
    if(nx<0.0){nx=0.0;}
    if(nx>1.0){nx=1.0;}
  }
}

void rm(string s,int del){
  int sid=sinv[s];
  prob[sid]=del;
  for(auto &nx : einv[sid]){
    for(int i=0;i<eqs[nx].size();i++){
      if(eqs[nx][i]==sid){
        swap(eqs[nx][i],eqs[nx].back());
        break;
      }
    }
    eqs[nx].pop_back();
    eqv[nx]-=del;
  }
  einv[sid].clear();
}

vector<string> unans;

void check(){
  while(true){
    vector<int> rmt;
    vector<int> rmf;
    for(int i=0;i<eqs.size();i++){
      if(eqv[i]==0){
        for(auto &nx : eqs[i]){
          if(alive[nx]==1){
            alive[nx]=0;
            rmf.push_back(nx);
          }
        }
      }
      else if(eqv[i]==eqs[i].size()){
        for(auto &nx : eqs[i]){
          if(alive[nx]==1){
            alive[nx]=0;
            rmt.push_back(nx);
            unans.push_back(slis[nx]);
          }
        }
      }
    }

    if(rmt.empty() && rmf.empty()){break;}
    for(auto &nx : rmt){
      rm(slis[nx],1);
    }
    for(auto &nx : rmf){
      rm(slis[nx],0);
    }
  }
}

int main(){
  current_clock();
  vector<int> remp(32,0);
  vector<vector<int>> vemp(32);

  for(int i=0;i<=99999;i++){
    int v=i;
    string cur;
    for(int j=0;j<5;j++){
      cur.push_back('0'+v%10);
      v/=10;
    }
    reverse(cur.begin(),cur.end());
    if(check(cur)){
      sinv[cur]=slis.size();
      slis.push_back(cur);
      alive.push_back(1);
      prob.push_back(30.0/30240.0);
    }
  }

  einv.resize(slis.size());

  int pac=0;
  for(int cq=0;;cq++){
    string q;
    if(cq==0){q="01234";}
    else if(!unans.empty()){
      q=unans.back();
      unans.pop_back();
    }
    else{
      long long tail=current_clock()+120000;
      int exc=0;
      while(current_clock()<tail){
        exc++;
        run();
        double tot=0.0;
        for(auto &nx : prob){tot+=nx;}
      }
      cerr << "Executed " << exc << " times\n";
      double sum=0.0;
      for(auto &nx : prob){sum+=nx;}
      cerr << sum << " : ";
      double best=-1.0;
      for(int i=0;i<slis.size();i++){
        if(alive[i]==0){continue;}
        if(best<prob[i]){
          q=slis[i];
          best=prob[i];
        }
      }
      cerr << best << "\n";
    }

    auto ca=ask(q);
    int ac=0;
    for(auto &nx : ca){
      if(nx==30){ac++;}
    }
    alive[sinv[q]]=0;
    int del=(ac-pac);
    pac=ac;

    vector<vector<int>> els(32);
    vector<int> cnt(32,0);
    for(auto &nx : ca){ cnt[nx]++; }
    for(auto &nx : unans){
      cnt[hbc(nx,q)]--;
    }
    for(int i=0;i<slis.size();i++){
      if(alive[i]){
        els[hbc(q,slis[i])].push_back(i);
      }
    }
    for(int i=0;i<30;i++){
      if(!els[i].empty()){
        for(auto &nx : els[i]){
          einv[nx].push_back(eqs.size());
        }
        eqs.push_back(els[i]);
        eqv.push_back(cnt[i]);
      }
    }

    rm(q,del);
    check();
  }
}
0