結果

問題 No.3501 Digit Products 2
コンテスト
ユーザー tnakao0123
提出日時 2026-04-20 11:16:56
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 29 ms / 2,000 ms
コード長 1,679 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 520 ms
コンパイル使用メモリ 69,556 KB
実行使用メモリ 30,308 KB
平均クエリ数 10.89
最終ジャッジ日時 2026-04-20 11:17:09
合計ジャッジ時間 7,510 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 72
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* -*- coding: utf-8 -*-
 *
 * 3501.cc:  No.3501 Digit Products 2 - yukicoder
 */

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

using namespace std;

/* constant */

const int MAX_N = 51;

/* typedef */

using vi = vector<int>;

/* global variables */

int tts[81 + 1], ps[MAX_N], xs[MAX_N];

/* subroutines */

int query(int n, int a, int b) {
  a = n - 1 - a, b = n - 1 - b;
  if (a > b) swap(a, b);
  printf("? %d %d\n", a, b); fflush(stdout);

  int p;
  scanf("%d", &p);
  if (p < 0) exit(0);
  return p;
}

void answer(int n, int xs[]) {
  if (n > 0) {
    printf("! ");
    for (int i = 0; i < n; i++) printf("%d", xs[i]);
    putchar('\n');
  }
  else
    puts("! -1");
  fflush(stdout);
}

/* main */

int main() {
  tts[1] = 1, tts[25] = 5, tts[49] = 7, tts[64] = 8, tts[81] = 9;
  
  int n;
  scanf("%d", &n);

  ps[0] = -1;
  vi vs(1, 0);
  for (int i = 1; i < n; i++) {
    ps[i] = query(n, 0, i);
    if (ps[i] > 0) vs.push_back(i);
  }

  int m = vs.size();
  if (m <= 1) {
    answer(-1, xs);
  }
  else if (m == 2) {
    int t = tts[ps[vs[1]]];
    if (t > 0) {
      xs[vs[0]] = xs[vs[1]] = t;
      answer(n, xs);
    }
    else
      answer(-1, xs);
  }
  else { // m >= 3
    int p1 = ps[vs[1]], p2 = ps[vs[2]];
    int p3 = query(n, vs[1], vs[2]);

    bool ok = false;
    for (int x0 = 1; ! ok && x0 <= 9; x0++)
      if (p1 % x0 == 0 && p2 % x0 == 0) {
	int x1 = p1 / x0, x2 = p2 / x0;
	if (x1 <= 9 && x2 <= 9 && x1 * x2 == p3) {
	  ok = true;
	  xs[vs[0]] = x0;
	  for (int i = 1; ok && i < m; i++) {
	    xs[vs[i]] = ps[vs[i]] / x0;
	    ok = (ps[vs[i]] % x0 == 0 && xs[vs[i]] <= 9);
	  }
	}
      }

    answer(n, xs);
  }
  
  return 0;
}
0