結果
問題 |
No.1187 皇帝ペンギン
|
ユーザー |
![]() |
提出日時 | 2020-08-22 15:10:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 1,000 ms |
コード長 | 1,482 bytes |
コンパイル時間 | 1,047 ms |
コンパイル使用メモリ | 105,252 KB |
実行使用メモリ | 25,452 KB |
平均クエリ数 | 16.54 |
最終ジャッジ日時 | 2024-07-17 06:23:43 |
合計ジャッジ時間 | 5,179 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 54 |
ソースコード
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <cmath> #include <map> #include <queue> #include <iomanip> #include <set> #include <tuple> #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; const ll MOD=1e9+7; template<class T> void chmin(T &a,const T &b){if(a>b) a=b;} template<class T> void chmax(T &a,const T &b){if(a<b) a=b;} map<int,int> mp; int ask(int x){ if(mp.count(x)) return mp[x]; cout<<"?"<<" "<<x<<endl; string s; cin>>s; if(s=="out") return mp[x]=0; else return mp[x]=1; } const int L=1e3; int main(){ vector<int> pri(L+20,1); for(int i=2;i<=L+10;i++){ if(pri[i]==0) continue; for(int j=2;i*j<=L+10;j++) pri[i*j]=0; } vector<int> prime={0}; for(int i=1;i<=L+10;i++) if(pri[i]) prime.push_back(i); int P=prime.size(); int ok=0,ng=P-1; while(abs(ok-ng)>2){ int mid=(ok+ng)/2; if(ask(prime[mid])) ok=mid; else{ if(ask(prime[mid+1])) ok=mid+1; else ng=mid+1; } } vector<int> table; for(int i=prime[ok];i<=prime[ng];i++) table.push_back(i); int T=table.size(); ok=0;ng=T-1; while(abs(ok-ng)>2){ int mid=(ok+ng)/2; if(ask(table[mid])) ok=mid; else{ if(ask(table[mid+1])) ok=mid+1; else ng=mid+1; } } if(ok-ng==2&&ask(table[ok+1])) ok++; int ans=table[ok]; cout<<"!"<<" "<<ans<<endl; return 0; }