結果
問題 |
No.513 宝探し2
|
ユーザー |
![]() |
提出日時 | 2024-09-30 01:15:10 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 2,240 bytes |
コンパイル時間 | 1,148 ms |
コンパイル使用メモリ | 111,140 KB |
実行使用メモリ | 25,220 KB |
平均クエリ数 | 40.08 |
最終ジャッジ日時 | 2024-09-30 01:15:13 |
合計ジャッジ時間 | 2,504 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:104:20: warning: 'use' may be used uninitialized [-Wmaybe-uninitialized] 104 | ll d2 = ask(x,m2); | ~~~^~~~~~ main.cpp:71:8: note: 'use' was declared here 71 | ll use; | ^~~ main.cpp:50:9: warning: 'n2' may be used uninitialized [-Wmaybe-uninitialized] 50 | if(m1>=m2){ | ^~ main.cpp:42:11: note: 'n2' was declared here 42 | ll n1,n2; | ^~
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; using ll = long long; #include<map> #include<cassert> int c; map<pair<ll,ll>,ll> memo; ll nx = 36571; ll ny = 78895; ll ask(ll x,ll y){ // ll d = abs(x-nx) + abs(y-ny); // if(d==0){ // cout<<c<<endl; // exit(0); // } if(memo.find({x,y})!=memo.end()) return memo[{x,y}]; c++; if(c>100){ assert(false); } cout<<x<<" "<<y<<endl; ll d; cin>>d; if(d==0){ exit(0); } return memo[{x,y}] = d; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll left = 0; ll right = 100000; int cnt = 0; ll n1,n2; while(right-left>2){ //cout<<left<<" "<<right<<endl; ll m1 = (21*left+13*right) / 34; ll m2 = (21*right+13*left) / 34; if(cnt==1) m2 = n1; if(cnt==2) m1 = n2; if(m1>=m2){ m1 = (21*left+13*right) / 34; m2 = (21*right+13*left) / 34; } if(m1==m2){ if(m2<right) m2++; else m1--; } n1 = m1; n2 = m2; ll d1 = ask(m1,0); ll d2 = ask(m2,0); if(d1<=d2) { right = m2; cnt = 1; }else{ left = m1; cnt = 2; } } ll use; ll mn = 1e9; for(ll x = left;x<=right;x++){ ll d = ask(x,0); if(d<mn){ mn = d; use = x; } } ll x = use; //cout<<x<<endl; left = 0; right = 100000; cnt = 0; while(right-left>2){ ll m1 = (21*left+13*right) / 34; ll m2 = (21*right+13*left) / 34; if(cnt==1) m2 = n1; if(cnt==2) m1 = n2; if(m1>=m2){ m1 = (21*left+13*right) / 34; m2 = (21*right+13*left) / 34; } if(m1==m2){ if(m2<right) m2++; else m1--; } n1 = m1; n2 = m2; ll d1 = ask(x,m1); ll d2 = ask(x,m2); if(d1<=d2){ right = m2; cnt = 1; }else{ left = m1; cnt = 2; } } for(ll y = left;y<=right;y++){ ll d = ask(x,y); } }