結果
| 問題 |
No.3212 SUPER Guess the Number
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 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 |
ソースコード
#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;
}