# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
118607 | 2019-06-19T09:44:30 Z | StevenH | The Big Prize (IOI17_prize) | C++14 | 6 ms | 512 KB |
#include "prize.h" #include <cstring> //#include <bits\stdc++.h> using namespace std; const int maxn = 200005; bool vis[maxn]; int lp; //rx right of r int find(int l,int r,int lx,int rx) //lx left of l { int mid,tmp,nm; mid=(l+r)/2; int k=0,tp=-1; while(mid-k>=l && mid+k<=r) { k++; if(!vis[mid+k] && mid<=r) { tp=mid+k; break; } else if(!vis[mid-k] && mid>=l) { tp=mid-k; break; } } if(tp==-1)return 0; /*while(vis[mid] && mid<=r)mid++; if(mid>r) { mid=(l+r)/2; while(vis[mid] && mid>=l)mid--; if(mid<l)return 0; // 0 not find any thing } if(mid<l || mid>199999)return 0;*/ mid=tp; vector<int> res = ask(mid); vis[mid]=true; if(res[0]+res[1]==0)return mid; else if(res[0]+res[1]==lp) { if(res[0]-lx>0) // left not empty { tmp=find(l,mid-1,lx,res[1]); if(tmp)return tmp; } if(res[1]-rx>0) // right not empty { tmp=find(mid+1,r,res[0],rx); if(tmp)return tmp; } } else if(tmp=find(l,r,lx,rx))return tmp; return 0; } int find_best(int n) { int mx=-1,nm,id; //vector<int> res = ask(i); for(int i=0;i<476;i++) { vector<int> res = ask(i); int tmp = res[0] + res[1]; if(tmp==0) { //cout<<i; return i; } if(tmp>mx) { mx=tmp; id=i; nm=1; } if(tmp==mx)nm++; } lp=mx; //lp refers to lollipop memset(vis,false,sizeof(vis)); int tp=find(476,n-1,476-nm,0); //cout<<tp; return tp; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 512 KB | answer is not correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 504 KB | answer is not correct |
2 | Halted | 0 ms | 0 KB | - |