제출 #367937

#제출 시각아이디문제언어결과실행 시간메모리
367937Marlov커다란 상품 (IOI17_prize)C++14
0 / 100
6 ms524 KiB
/* Code by @marlov */ #include <iostream> #include <fstream> #include <string> #include <sstream> #include <vector> #include <string> #include <cmath> #include <algorithm> #include <iomanip> #include <utility> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <stack> #include <queue> #include <iterator> #include <bitset> #include "prize.h" using namespace std; typedef long long ll; typedef pair<int,int> ii; int N; int sN; int mvs=0; int result=-1; /* vector<int> ask(int i){ cout<<"query: "<<i<<endl; int rlv,rrv; cin>>rlv>>rrv; return {rlv,rrv}; } */ unordered_map<int,int> lv; unordered_map<int,int> rv; vector<int> query(int i){ if(!(lv.count(i)==1&&rv.count(i)==1)){ vector<int> askv=ask(i); lv[i]=askv[0]; rv[i]=askv[1]; } if(lv[i]+rv[i]==0) result=i; return {lv[i],rv[i]}; } void binary_search(int l,int r){ //cout<<"seeing:"<<l<<","<<r<<endl; if(result!=-1) return; if(l>=N||l<0||r>=N||r<0) return; if(l>=r) return; vector<int> lb=query(l); vector<int> rb=query(r); if(lb[0]+lb[1]<mvs) binary_search(l+1,r); if(rb[0]+rb[1]<mvs) binary_search(l,r-1); int mid=(l+r)/2; if(rb[0]-lb[0]==0) return; binary_search(l,mid); binary_search(mid+1,r); } //method can use int[] ask(int i) which return left and right value int find_best(int n){ int N=n; int sN=floor(sqrt((double)N)); //loop first sqrtN value to find max dude for(int i=0;i<N;i+=sN){ vector<int> qv=query(i); mvs=max(mvs,qv[0]+qv[1]); } //loop through sqrtN for(int i=0;i<N;i+=sN){ binary_search(i,(i+sN<N?i+sN:N-1)); } return result; } /* int main() { ios_base::sync_with_stdio(0); cin.tie(0); int val=find_best(8); cout<<"ANSWER:"<<val<<endl; return 0; } */ /* stuff you should look for * int overflow, array bounds * special cases (n=1,n=0?) * do smth instead of nothing and stay organized */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...