結果

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

ソースコード

diff #
raw source code 

  #include <bits/stdc++.h>
  using namespace std;

  int ask(int a, int b) {
      cout << "? " << a << " " << b << '\n' << flush;
      int p;
      if (!(cin >> p)) exit(0);
      if (p == -1) exit(0); // judge says invalid / terminated
      return p;
  }

  int main() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);

      int N;
      cin >> N;

      vector<int> p(N - 1);
      vector<int> nz;
      for (int i = 0; i <= N - 2; i++) {
          p[i] = ask(i, N - 1);
          if (p[i] > 0) nz.push_back(i);
      }

      vector<int> d(N, 0);

      if ((int)nz.size() >= 2) {
          int u = nz[0], v = nz[1];
          int r = ask(u, v);

          int lead = -1;
          for (int a = 1; a <= 9; a++) {
              if (p[u] % a) continue;
              if (p[v] % a) continue;
              int du = p[u] / a, dv = p[v] / a;
              if (1 <= du && du <= 9 && 1 <= dv && dv <= 9 && du * dv == r) {
                  lead = a;
                  break;
              }
          }

          if (lead == -1) {
              cout << "! -1\n" << flush;
              return 0;
          }

          d[N - 1] = lead;
          for (int i = 0; i <= N - 2; i++) {
              if (p[i] % lead != 0) { cout << "! -1\n" << flush; return 0; }
              d[i] = p[i] / lead;
              if (d[i] < 0 || d[i] > 9) { cout << "! -1\n" << flush; return 0; }
          }

          string ans;
          ans.reserve(N);
          for (int i = N - 1; i >= 0; i--) ans.push_back(char('0' + d[i]));
          cout << "! " << ans << '\n' << flush;
          return 0;
      }

      if ((int)nz.size() == 0) {
          cout << "! -1\n" << flush;
          return 0;
      }

      // |nz| == 1
      int t = nz[0];
      int pt = p[t];

      vector<pair<int,int>> cand; // (lead, d_t)
      for (int lead = 1; lead <= 9; lead++) {
          if (pt % lead) continue;
          int dt = pt / lead;
          if (1 <= dt && dt <= 9) cand.push_back({lead, dt});
      }

      if (cand.size() != 1) {
          cout << "! -1\n" << flush;
          return 0;
      }

      d.assign(N, 0);
      d[N - 1] = cand[0].first;
      d[t] = cand[0].second;

      string ans;
      ans.reserve(N);
      for (int i = N - 1; i >= 0; i--) ans.push_back(char('0' + d[i]));
      cout << "! " << ans << '\n' << flush;
      return 0;
  }
0