結果

問題 No.3212 SUPER Guess the Number
ユーザー D M
提出日時 2025-09-26 16:18:35
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,326 bytes
コンパイル時間 3,715 ms
コンパイル使用メモリ 275,860 KB
実行使用メモリ 26,200 KB
平均クエリ数 22.00
最終ジャッジ日時 2025-09-26 16:18:42
合計ジャッジ時間 5,839 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

  const ll A_MIN = 1, A_MAX = 1'000'000;

  // 1回目：返答は来ない
  ll x = 0;
  cout << "? " << x << endl;

  ll L = A_MIN, R = A_MAX;

  // 符号交互に 2^k を足していく：+2^19, -2^18, +2^17, ...
  for (int k = 19; k >= 0; --k) {
    ll s = ( ( (19 - k) % 2 ) == 0 ? (1LL << k) : -(1LL << k) );
    ll y = x + s;

    cout << "? " << y << endl;
    int res; 
    if (!(cin >> res)) return 0;   // 早期終了（-1 など）にも備える

    // 判定境界は t = x + s/2 （sは2の冪なので整数）
    ll t = x + s / 2;

    if (s > 0) {
      if (res == 1) {
        // 近づいた ⇒ a >= t
        L = max(L, t);
      } else {
        // 遠ざかった ⇒ a <= t-1
        R = min(R, t - 1);
      }
    } else { // s < 0
      if (res == 1) {
        // 近づいた ⇒ a <= t
        R = min(R, t);
      } else {
        // 遠ざかった ⇒ a >= t+1
        L = max(L, t + 1);
      }
    }

    // 次の「直前点」
    x = y;
  }

  // 20回で L==R になる（はず）。保険で範囲内に丸める。
  if (L < A_MIN) L = A_MIN;
  if (R > A_MAX) R = A_MAX;
  ll a = L;  // L==R を想定

  cout << "! " << a << endl;
  return 0;
}
0