結果
問題 | No.253 ロウソクの長さ |
ユーザー |
![]() |
提出日時 | 2016-05-05 23:17:53 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 1,836 bytes |
コンパイル時間 | 1,474 ms |
コンパイル使用メモリ | 158,968 KB |
実行使用メモリ | 25,220 KB |
平均クエリ数 | 32.28 |
最終ジャッジ日時 | 2024-07-16 23:41:08 |
合計ジャッジ時間 | 4,297 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>typedef long long ll;typedef unsigned long long ull;#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)#define REP(i,n) FOR(i,0,n)#define RANGE(vec) (vec).begin(),(vec).end()using namespace std;class LengthOfCandle{public:int ask(int Y){cout << "? " << Y << endl;int res;cin >> res;return res;}void solve(void){int t = 0;// X <= 10^9 なので最大 30 回ほどクエリを投げることになる// X = 30 以下のときは 30 回のクエリ施行中にろうそくの長さが 0 に// なってしまうことがあるので最初に特別なケースをつぶすint x = ask(90);++t;// 90 以下なので 0 と比較しながら答えをたしかめればよいif ( x == 0 ){cout<<"! "<<90<<endl;return;}if ( x < 0 ){for (; t < 90; ++t){x = ask(0);if ( x == 0 ){cout<<"! "<<t<<endl;return;}}}// 後は二分探索ll u = 1E+9+1;ll l = 90;for (; t < 100; ++t){// X = Y + tll mid = (l+u)/2;int res = ask(mid-t);if ( res == 0 ){u = mid;break;}if ( res > 0 )l = mid;elseu = mid;if (u == l)break;}cout<<"! "<<u<<endl;}};#if 1int main(int argc, char *argv[]){ios::sync_with_stdio(false);auto obj = new LengthOfCandle();obj->solve();delete obj;return 0;}#endif