Submission #1200474

#TimeUsernameProblemLanguageResultExecution timeMemory
1200474mertbbmThe Big Prize (IOI17_prize)C++20
0 / 100
2 ms476 KiB
#include "prize.h" #include <bits/stdc++.h> //#include "grader.cpp" using namespace std; //#define int long long #define ld long double #define show(x,y) cout << y << " " << #x << endl; #define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl; #define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl; #define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl; typedef pair<int,int>pii; typedef pair<ld,ld>pi2; mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); int ran(int index){return rng()%index;} //ask() int blk=290; int sz=480; map<int,vector<int>>mp; vector<int>f(int index){ if(mp.find(index)!=mp.end()) return mp[index]; return mp[index]=ask(index); } int32_t find_best(int32_t n){ //pii maxi={-1,-1}; //for(int x=0;x<min(n,sz);x++){ //vector<int>hold=f(x); //maxi=max(maxi,{hold[0]+hold[1],x}); //if(hold[0]+hold[1]==0) return x; //} vector<int>nxt=f(sz); int cur=sz; while(cur<n){ vector<int>take=nxt; if(cur+blk<n) nxt=f(cur+blk); else nxt={(int)1e9,(int)1e9}; if(take==nxt){ cur+=blk; continue; } int target=min(cur+blk,n); int counter2=0; while(cur<target){ counter2++; vector<int>check; if(cur==target-blk) check=take; else check=f(cur); if(check[0]+check[1]==0) return cur; //if(check[0]+check[1]!=maxi.first){ //cur++; //continue; //} if(check==nxt){ cur=target; continue; } int l=cur+1; int r=target-1; int best=r; int mid; int counter=0; while(l<=r){ counter++; mid=(l+r)/2; vector<int>hold=f(mid); if(hold==check){ l=mid+1; } else{ best=mid; if(hold[0]+hold[1]==0) return mid; r=mid-1; } } assert(counter<=9); cur=min(best+2,target); } } return -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...