#1157317 (C++17) No.3496 協力カード当て

• 問題: No.3496 協力カード当て
• ユーザー: 👑 Nachia
• 提出日時: 2026-04-14 22:30:56
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,618 ms / 2,000 ms
• コード長: 3,901 bytes
• コンパイル時間: 1,110 ms
• コンパイル使用メモリ: 112,056 KB
• 実行使用メモリ: 69,980 KB
• スコア: 200
• 平均クエリ数: 31.50
• 最終ジャッジ日時: 2026-04-14 23:52:24
• 合計ジャッジ時間: 7,854 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
other	AC * 16

ソースコード

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

using Hand = array<unsigned char, 11>;
const bool dbg = 0;

void testcase(){
  ll id, N, M; cin >> id >> N >> M;
  V<ll> A(N); REP(i,N) cin >> A[i];
  sort(A.begin(), A.end());
  Hand myhand; myhand.fill(0); for(auto a : A) myhand[a-1]++;
  
  V<Hand> U; {
    V<ll> ft(N+M-1);
    for(ll i=M-1; i<ft.size(); i++) ft[i] = 1;
    Hand Q;
    do {
      Q.fill(0);
      ll pt = 0;
      for(ll x : ft) if(x == 1) Q[pt]++; else pt++;
      bool ok = 1;
      REP(i,M) if(Q[i] > i+1){ ok = 0; break; }
      if(ok) U.push_back(Q);
    } while(next_permutation(ft.begin(), ft.end()));
  }
  
  ll myhandid = find(U.begin(), U.end(), myhand) - U.begin();
  ll myhandcy = 1;
  ll ophandid = 0;
  ll ophandcy = 1;

  //cout << U.size() << endl;

  V<ll> X(M);
  V<ll> unrevealed;
  REP(i,M) unrevealed.push_back(i);
  sort(unrevealed.begin(), unrevealed.end());

  auto outputhand = [&](Hand hand) -> void {
    REP(i,M) REP(t,hand[i]) cout << " " << (i+1);
  };

  auto rec = [&](bool ismyturn) -> void {
    string x; cin >> x;
    if(x[0] == 'G'){
      string x; cin >> x >> x;
    }
    if(x[0] == 'C'){
      ll x, k; cin >> x >> k; x--;
      X[x] = k;

      ll pt = x, ptin = M;
      if(unrevealed.size()){
        pt = find(unrevealed.begin(), unrevealed.end(), x) - unrevealed.begin();
        ptin = unrevealed.size();
      }

      if(!ismyturn){
        ophandid += ophandcy * pt;
        ophandcy *= ptin;
      }

      if(unrevealed.size()){
        unrevealed.erase(find(unrevealed.begin(), unrevealed.end(), x));
        sort(unrevealed.begin(), unrevealed.end());
      }
    }
  };

  while(1){
    string s; cin >> s;
    if(s == "END") break;
    if(s == "TURN"){
      if(dbg){ cout << "my turn" << endl; }
      if(dbg){ cout << "   unrevealed.size() = " << unrevealed.size() << endl; }
      if(dbg){ cout << "   U.size() = " << U.size() << endl; }
      if(dbg){ cout << "   myhand = " << myhandid << " / " << myhandcy << endl; }
      if(dbg){ cout << "   ophand = " << ophandid << " / " << ophandcy << endl; }
      if(unrevealed.empty() && myhandcy >= U.size() && ophandcy >= U.size()){
        Hand res; res.fill(0); REP(i,M) res[i] = X[i] - U[myhandid][i] - U[ophandid][i];
        if(dbg){ cout << "Guessing : "; }
        if(dbg){ cout << "  X = "; for(auto a : X){ cout << (int)a << " "; } cout << endl; }
        if(dbg){ cout << "  myhand = "; for(auto a : U[myhandid]){ cout << (int)a << " "; } cout << endl; }
        if(dbg){ cout << "  ophand = "; for(auto a : U[ophandid]){ cout << (int)a << " "; } cout << endl; }
        cout << "GUESS"; outputhand(res); cout << endl;
      }
      else if(unrevealed.size()){
        ll h = (myhandid / myhandcy) % unrevealed.size();
        cout << "ASK " << (unrevealed[h] + 1) << endl;
        myhandcy *= unrevealed.size();
      }
      else {
        ll h = (myhandid / myhandcy) % M;
        cout << "ASK " << (h + 1) << endl;
        myhandcy *= M;
      }
    } else {
      if(dbg){ cout << "not my turn" << endl; }
      if(dbg){ cout << "   unrevealed.size() = " << unrevealed.size() << endl; }
      if(dbg){ cout << "   U.size() = " << U.size() << endl; }
      if(dbg){ cout << "   myhand = " << myhandid << " / " << myhandcy << endl; }
      if(dbg){ cout << "   ophand = " << ophandid << " / " << ophandcy << endl; }
    }
    rec(s == "TURN");
  }
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  testcase();
  return 0;
}