# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
790849 | PoonYaPat | The Big Prize (IOI17_prize) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "prize.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
int mmax=0,n,non_lol;
vector<int> val[200005];
vector<int> none;
void Ask(int x) {
if (!val[x].size()) val[x]=ask(x);
}
void solve(int l, int r) { //l and r must be lolli_pop
Ask(l);
Ask(r);
if (val[r][0]==val[l][0]) return;
if (val[r][0]-val[l][0]==r-l-1) {
for (int i=l+1; i<r; ++i) none.push_back(i);
} else {
int mid=(l+r)/2;
Ask(mid);
if (val[mid][0]+val[mid][1]!=mmax) {
none.push_back(mid);
for (int i=mid-1; i>l; --i) {
Ask(i);
if (val[i][0]+val[i][1]!=mmax) none.push_back(i);
else {
solve(l,i);
break;
}
}
for (int i=mid+1; i<r; ++i) {
Ask(i);
if (val[i][0]+val[i][1]!=mmax) none.push_back(i);
else {
solve(i,r);
break;
}
}
} else {
solve(l,mid);
solve(mid,r);
}
}
}
int find_best(int N) {
n=N;
for (int i=0; i<min(500,n); ++i) {
val[i]=ask(i);
mmax=max(mmax,val[i][0]+val[i][1]);
}
int st,ed;
for (int i=0; i<n; ++i) {
Ask(i);
if (val[i][0]+val[i][1]!=mmax) none.push_back(i);
else {
st=i;
break;
}
}
int l=0, r=n-1;
int cnt=0;
while (l<r) {
int mid=(l+r+1)/2;
//assert(cnt<1000);
assert(0<=mid && mid<n);
Ask(mid);
if (val[mid][0]+val[mid][1]==mmax) l=mid;
else if (val[mid][1]==0) r=mid-1;
else l=mid;
}
ed=l;
solve(st,ed);
for (auto s : none) {
Ask(s);
if (val[s][0]+val[s][1]==0) return s;
}
}