#1157306 (C++14) No.3496 協力カード当て

• 問題: No.3496 協力カード当て
• ユーザー: hos.lyric
• 提出日時: 2026-04-14 22:00:19
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,987 ms / 2,000 ms
• コード長: 5,445 bytes
• コンパイル時間: 1,113 ms
• コンパイル使用メモリ: 157,264 KB
• 実行使用メモリ: 330,676 KB
• スコア: 164
• 平均クエリ数: 35.44
• 最終ジャッジ日時: 2026-04-15 09:47:02
• 合計ジャッジ時間: 7,910 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T> ostream &operator<<(ostream &os, const vector<T> &as);
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// [l, r)^n, sum = s
template <class F> void doArraysWithSumRec(int n, int l, int r, int s, F f, int i, vector<int> &as) {
  if (i == n) {
    f(as);
  } else {
    const int ll = max(l, s - (n - i - 1) * (r - 1));
    const int rr = min(r - 1, s - (n - i - 1) * l);
    for (as[i] = ll; as[i] <= rr; ++as[i]) doArraysWithSumRec(n, l, r, s - as[i], f, i + 1, as);
  }
}
template <class F> void doArraysWithSum(int n, int l, int r, int s, F f) {
  vector<int> as(n);
  if (n * l <= s && s <= n * (r - 1)) doArraysWithSumRec(n, l, r, s, f, 0, as);
}


void exper() {
  for (int M = 4; M <= 11; ++M) for (int N = 2; N <= 18; ++N) if (3*N <= M*(M+1)/2) {
    Int way = 0;
    doArraysWithSum(M, 0, N + 1, N, [&](const vector<int> &fs) -> void {
      for (int m = 1; m <= M; ++m) if (fs[m - 1] > m) return;
      ++way;
    });
    Int fac = 1;
    for (int i = 1; i <= M; ++i) fac *= i;
    cerr << "M = " << M << ", N = " << N << ": way = " << way << ", fac = " << fac << endl;
    assert(way <= fac);
  }
}


int main() {
  // exper();
  
  int I, N, M;
  scanf("%d%d%d", &I, &N, &M);
  vector<int> C(N);
  for (int n = 0; n < N; ++n) scanf("%d", &C[n]);
  
  /*
  vector<vector<int>> F;
  doArraysWithSum(M, 0, N + 1, N, [&](vector<int> fs) -> void {
    fs.insert(fs.begin(), 0);
    for (int m = 1; m <= M; ++m) if (fs[m] > m) return;
    F.push_back(fs);
  });
  const int FLen = F.size();
  */
  int FLen = 0;
  doArraysWithSum(M, 0, N + 1, N, [&](const vector<int> &fs) -> void {
    for (int m = 1; m <= M; ++m) if (fs[m - 1] > m) return;
    ++FLen;
  });
  vector<basic_string<int>> P;
  P.reserve(FLen);
  {
    basic_string<int> ps(M, -1);
    for (int m = 1; m <= M; ++m) ps[m - 1] = m;
    do {
      P.push_back(ps);
      if ((int)P.size() >= FLen) break;
    } while (next_permutation(ps.begin(), ps.end()));
  }
  
  vector<int> freq(M + 1, 0);
  for (int n = 0; n < N; ++n) ++freq[C[n]];
  // const int my = lower_bound(F.begin(), F.end(), freq) - F.begin();
  int my = -1;
  {
    int id = -1;
    doArraysWithSum(M, 0, N + 1, N, [&](const vector<int> &fs) -> void {
      for (int m = 1; m <= M; ++m) if (fs[m - 1] > m) return;
      ++id;
      for (int m = 1; m <= M; ++m) if (fs[m - 1] != freq[m]) return;
      my = id;
    });
  }
  
  vector<int> total(M + 1, -1);
  basic_string<int> ms;
  for (int q = 0; q < (M-1) * 2; ++q) {
    char msg[10];
    scanf("%s", msg);
    if (string(msg) == "TURN") {
      const int m = P[my][q / 2];
      printf("ASK %d\n", m);
      fflush(stdout);
      int X, K;
      scanf("%*s%d%d", &X, &K);
      assert(m == X);
      if (!~total[m]) total[m] = K;
      assert(total[m] == K);
    } else if (string(msg) == "WAIT") {
      int X, K;
      scanf("%*s%d%d", &X, &K);
      const int m = X;
      ms.push_back(m);
      if (!~total[m]) total[m] = K;
      assert(total[m] == K);
    } else {
      assert(false);
    }
  }
  {
    const int m0 = P[my][M - 1];
    total[m0] = 3*N;
    for (int m = 1; m <= M; ++m) if (m0 != m) total[m0] -= total[m];
  }
  
  const int your = lower_bound(P.begin(), P.end(), ms) - P.begin();
  vector<int> ans;
  // for (int m = 1; m <= M; ++m) freq[m] = total[m] - freq[m] - F[your][m];
  vector<int> Fyour;
  {
    int id = -1;
    doArraysWithSum(M, 0, N + 1, N, [&](const vector<int> &fs) -> void {
      for (int m = 1; m <= M; ++m) if (fs[m - 1] > m) return;
      ++id;
      if (id == your) {
        Fyour = fs;
        Fyour.insert(Fyour.begin(), 0);
      }
    });
  }
  for (int m = 1; m <= M; ++m) freq[m] = total[m] - freq[m] - Fyour[m];
// cerr<<"total = "<<total<<", F[your] = "<<F[your]<<", freq = "<<freq<<endl;
  for (int m = 1; m <= M; ++m) for (int f = 0; f < freq[m]; ++f) ans.push_back(m);
  assert((int)ans.size() == N);
  
  for (int q = 0; q < 2; ++q) {
    char msg[10];
    scanf("%s", msg);
    if (string(msg) == "TURN") {
      printf("GUESS");
      for (int n = 0; n < N; ++n) printf(" %d", ans[n]);
      puts("");
      fflush(stdout);
      scanf("%*s%*s%*s");
    } else if (string(msg) == "WAIT") {
      scanf("%*s%*s%*s");
    } else {
      assert(false);
    }
  }
  return 0;
}