結果

問題 No.3347 Guess The Array
コンテスト
ユーザー tnakao0123
提出日時 2025-11-15 19:01:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 486 ms / 2,000 ms
コード長 1,464 bytes
コンパイル時間 719 ms
コンパイル使用メモリ 63,556 KB
実行使用メモリ 25,996 KB
平均クエリ数 3887.09
最終ジャッジ日時 2025-11-15 19:01:55
合計ジャッジ時間 17,994 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 46
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘bool query(vi&)’:
main.cpp:33:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   33 |   scanf("%s", s);
      |   ~~~~~^~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:47:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   47 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3347.cc:  No.3347 Guess The Array - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 500;
const int CNT = 5000;

/* typedef */

using vi = vector<int>;

/* global variables */

int cs[MAX_N + 1];

/* subroutines */

bool query(vi &v) {
  printf("? %d", (int)v.size());
  for (auto u: v) printf(" %d", u);
  putchar('\n'); fflush(stdout);

  char s[8];
  scanf("%s", s);
  return (s[0] == 'Y');
}

void answer(vi &as) {
  printf("!");
  for (auto a: as) printf(" %d", a);
  putchar('\n'); fflush(stdout);
}

/* main */

int main() {
  int n;
  scanf("%d", &n);

  int csum = 0;
  for (int i = 1; csum < n && i <= n; i++) {
    cs[i] = 0;
    while (cs[i] < n) {
      vi v(cs[i] + 1, i);
      if (query(v)) cs[i]++;
      else break;
    }
    csum += cs[i];
  }

  //vi as(n);
  //for (int i = 1; i <= n; i++) as[i - 1] = cs[i];
  //answer(as);

  vi ss;
  for (int i = 1; ss.size() < n && i <= n; i++)
    if (cs[i]) {
      if (ss.empty())
	ss.assign(cs[i], i);
      else {
	vi ss0(ss);
	for (int k = 1; k <= cs[i]; k++) {
	  int p0 = 0, p1 = ss.size() + 1;
	  while (p0 + 1 < p1) {
	    int p = (p0 + p1) / 2;

	    vi v(ss.begin(), ss.begin() + p);
	    for (int j = 0; j < k; j++) v.push_back(i);
	    if (query(v)) p0 = p;
	    else p1 = p;
	  }
	  ss0.insert(ss0.begin() + p0, i);
	}
	swap(ss, ss0);
      }
    }

  answer(ss);
  
  return 0;
}
0