結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー butsurizuki
提出日時 2025-12-08 23:56:41
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 2,860 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,978 ms
コンパイル使用メモリ 306,472 KB
実行使用メモリ 38,720 KB
スコア 0
最終ジャッジ日時 2025-12-25 01:30:46
合計ジャッジ時間 15,414 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 99
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:105:20: warning: ‘qid’ may be used uninitialized [-Wmaybe-uninitialized]
  105 |     cerr << val[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{
      for(int i=0;i<s.size();i++){
        if(val[i]==-1){qid=i; break;}
      }
    }

    cerr << val[qid] << "\n";
    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]=1;}
    }
    if(hb[0].first==5){return 0;}

    val[qid]=cur-done;
    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