結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー butsurizuki
提出日時 2025-12-14 01:47:12
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 382 ms / 5,000 ms
コード長 3,187 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,344 ms
コンパイル使用メモリ 307,284 KB
実行使用メモリ 34,632 KB
スコア 9,995,482
平均クエリ数 45.18
最終ジャッジ日時 2025-12-25 01:32:33
合計ジャッジ時間 35,986 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:115:18: warning: ‘qid’ may be used uninitialized [-Wmaybe-uninitialized]
  115 |     cout << s[qid] << "\n";
      |                  ^
main.cpp:94:9: note: ‘qid’ was declared here
   94 |     int qid;
      |         ^~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>

using namespace std;

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;
}

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;
}

using pi=pair<int,int>;

vector<int> val;

vector<set<int>> groups;
vector<int> sums;
vector<vector<int>> ginv;

vector<int> uncall;

void work(){
  while(true){
    // check
    vector<pi> know;
    for(int i=0;i<groups.size();i++){
      if(sums[i]==0){
        for(auto &nx : groups[i]){
          if(val[nx]==-1){
            val[nx]=0;
            know.push_back({nx,0});
          }
        }
      }
      else if(sums[i]==groups[i].size()){
        for(auto &nx : groups[i]){
          if(val[nx]==-1){
            val[nx]=1;
            know.push_back({nx,1});
          }
        }
      }
    }

    if(know.empty()){break;}

    // resolve
    for(auto &nx : know){
      if(nx.second==1){uncall.push_back(nx.first);}
      for(auto &ny : ginv[nx.first]){
        groups[ny].erase(nx.first);
        sums[ny]-=nx.second;
      }
    }
  }
}

int main(){
  vector<string> s;
  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)){s.push_back(cur);}
  }

  val.resize(s.size());
  for(auto &nx : val){nx=-1;}
  ginv.resize(s.size());
  for(auto &nx : ginv){nx.clear();}

  int done=0;
  vector<int> known;
  while(true){
    int qid;
    if(!uncall.empty()){
      qid=uncall.back();
      uncall.pop_back();
    }
    else{
      double best=-1.0;
      for(int i=0;i<s.size();i++){
        if(val[i]==-1){
          double cur=0.0;
          for(auto &nx : ginv[i]){
            cur+=(((double)sums[nx])/groups[nx].size());
          }
          if(best<cur){
            best=cur;
            qid=i;
          }
        }
      }
    }

    cout << s[qid] << "\n";
    fflush(stdout);

    int cur=0;
    vector<int> bk(32,0);
    vector<pair<int,int>> hb(30);
    for(auto &nx : hb){
      cin >> nx.first >> nx.second;
      if(nx.first==5){cur++;}
      else{bk[nx.first*6+nx.second]++;}
    }
    if(hb[0].first==5){return 0;}

    if(val[qid]==-1){
      val[qid]=cur-done;
      for(auto &nx : ginv[qid]){
        groups[nx].erase(qid);
        sums[nx]-=val[qid];
      }
    }
    if(cur!=done){ known.push_back(qid); }
    done=cur;
    for(auto &nx : known){
      bk[hbc(s[qid],s[nx])]++;
    }
    work();

    // generate
    vector<vector<int>> cgrp(32);
    for(int i=0;i<s.size();i++){
      if(val[i]!=-1){
        bk[hbc(s[qid],s[i])]-=val[i];
      }
      else{
        cgrp[hbc(s[qid],s[i])].push_back(i);
      }
    }
    for(int i=0;i<30;i++){
      if(!cgrp[i].empty()){
        set<int> app;
        for(auto &nx : cgrp[i]){
          ginv[nx].push_back(groups.size());
          app.insert(nx);
        }
        groups.push_back(app);
        sums.push_back(bk[i]);
      }
    }
    work();
  }
}
0