제출 #289138

#제출 시각아이디문제언어결과실행 시간메모리
289138eohomegrownapps커다란 상품 (IOI17_prize)C++14
20 / 100
86 ms2048 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; vector<int> lcache; vector<int> rcache; int n; pair<int,int> askmap(int i){ if (lcache[i]==-1){ vector<int> res = ask(i); lcache[i] = res[0]; rcache[i] = res[1]; } return {lcache[i],rcache[i]}; } int asksum(int i){ auto p = askmap(i); return p.first+p.second; } int find_best(int N) { n=N; lcache.resize(n,-1); rcache.resize(n,-1); if (n<=600){ for (int i = 0; i < n; i++) { if(asksum(i) == 0){ return i; } } assert(1==0); } int maxsum = 0; int maxind = -1; for (int i = 0; i<600; i++){ int res = asksum(i); if (res==0){return i;} if (res>maxsum){ maxsum=res; maxind=i; } } // first ind is at maxind int ptr = maxind; while (ptr<n){ //cout<<ptr<<endl; auto res = askmap(ptr); if (res.first+res.second==0){return ptr;} if (res.first+res.second<maxsum){ ptr++; continue; } // otherwise find stretch equal to this value int l = 0, r = 1; while (ptr+r<n){ auto rs = askmap(ptr); if (rs.first+rs.second==0){return ptr;} if (rs!=res){ break; } r<<=1; } r=min(r,n-1); while (l<=r){ int m = (l+r)/2; if (asksum(ptr+m)==0){return ptr+m;} if (askmap(ptr+m)!=res){ r=m-1; } else { l=m+1; } } ptr+=l; } assert(1==0); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...