#1157354 (C++23) No.3496 協力カード当て

• 問題: No.3496 協力カード当て
• ユーザー: Kude
• 提出日時: 2026-04-14 23:15:26
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 133 ms / 2,000 ms
• コード長: 3,894 bytes
• コンパイル時間: 3,500 ms
• コンパイル使用メモリ: 351,692 KB
• 実行使用メモリ: 30,064 KB
• スコア: 224
• 平均クエリ数: 27.62
• 最終ジャッジ日時: 2026-04-14 23:54:46
• 合計ジャッジ時間: 7,354 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

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

ソースコード

#include<bits/stdc++.h>
namespace {
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int id, n, m;
  cin >> id >> n >> m;
  VI c(n);
  rep(i, n) cin >> c[i];
  int cnt = 0;
  array<int, 12> cf{};
  for (int x : c) cf[x]++;
  array<int, 12> now{};
  int cid = -1;
  auto dfs1 = [&](auto&& self, int i, int rest) -> void {
    if (rest == 0 || i == m) {
      if (rest <= m) {
        now[i] = rest;
        if (now == cf) cid = cnt;
        cnt++;
      }
      now[i] = 0;
      return;
    }
    rep(c, min(i, rest) + 1) now[i] = c, self(self, i + 1, rest - c);
    now[i] = 0;
  };
  dfs1(dfs1, 1, n);
  int t = 0, m2t = 1;
  while (m2t < cnt) t++, m2t *= m;
  VI v1, v2;
  int memo[12];
  rep(i, 12) memo[i] = -1;
  auto ask = [&](int i) {
    cout << "ASK " << i << endl;
  };
  int cid_tmp = cid;
  rep(_, t) {
    string turn;
    cin >> turn;
    if (turn == "TURN") {
      assert(id == 1);
      ask(cid_tmp % m + 1);
      cid_tmp /= m;
    } else {
      assert(turn == "WAIT" && id == 2);
    }
    cin >> turn;
    assert(turn == "COUNT");
    int x, k;
    cin >> x >> k;
    memo[x] = k;
    v1.emplace_back(x-1);

    cin >> turn;
    if (turn == "TURN") {
      assert(id == 2);
      ask(cid_tmp % m + 1);
      cid_tmp /= m;
    } else {
      assert(turn == "WAIT" && id == 1);
    }
    cin >> turn;
    assert(turn == "COUNT");
    cin >> x >> k;
    memo[x] = k;
    v2.emplace_back(x-1);
  }

  int id1 = 0, id2 = 0;
  for (int x : v1 | views::reverse) id1 = m * id1 + x;
  for (int x : v2 | views::reverse) id2 = m * id2 + x;

  cnt = 0;
  array<int, 12> f1{}, f2{};
  auto dfs2 = [&](auto&& self, int i, int rest) -> void {
    if (rest == 0 || i == m) {
      if (rest <= m) {
        now[i] = rest;
        if (cnt == id1) f1 = now;
        if (cnt == id2) f2 = now;
        cnt++;
      }
      now[i] = 0;
      return;
    }
    rep(c, min(i, rest) + 1) now[i] = c, self(self, i + 1, rest - c);
    now[i] = 0;
  };
  dfs2(dfs2, 1, n);
  if (id == 1) assert(f1 == cf);
  else assert(f2 == cf);
  array<int, 12> f3{};
  rep(i, m+1) if (f1[i] + f2[i] == i) memo[i] = i;
  rep(i, m+1) if (memo[i] != -1) {
    f3[i] = memo[i] - f1[i] - f2[i];
  }
  while (accumulate(all(f3), 0) != n) {
    VI cands;
    rep(i, m+1) if (memo[i] == -1) cands.emplace_back(i);
    if (ssize(cands) == 1) {
      f3[cands[0]] = n - accumulate(all(f3), 0);
      continue;
    }
    int acc = 0;
    for (int v : cands) acc += v - f1[v] - f2[v];
    if (acc + accumulate(all(f3), 0) == n) {
      for (int v : cands) f3[v] = v - f1[v] - f2[v];
      continue;
    }
    int v = *ranges::max_element(cands, greater{}, [&](int v) { return v - f1[v] - f2[v]; });
    string turn;
    cin >> turn;
    if (turn == "TURN") {
      ask(v);
    } else {
      assert("WAIT");
    }
    cin >> turn;
    assert(turn == "COUNT");
    int x, k;
    cin >> x >> k;
    assert(x == v);
    memo[x] = k;
    f3[x] = memo[x] - f1[x] - f2[x];
  }
  rep(_, 2) {
    string turn;
    cin >> turn;
    if (turn == "TURN") {
      VI ans;
      rep(i, m+1) rep(_, f3[i]) ans.emplace_back(i);
      assert(ssize(ans) == n);
      cout << "GUESS";
      for (int x : ans) cout << ' ' << x;
      cout << endl;
    } else {
      assert(turn == "WAIT");
    }
    cin >> turn;
    assert(turn == "GUESSED");
    int x, k;
    cin >> x >> k;
  }
}