# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1238120 | vivkostov | The Big Prize (IOI17_prize) | C++20 | 0 ms | 0 KiB |
#include "prize.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
mt19937 mt(time(nullptr));
int sum,lamp;
vector<int>a;
void prec()
{
for(int i=1;i<=5;i++)
{
a=(ask(mt()%n));
sum=max(sum,a[0]+a[1]);
}
}
void rec(int l,int r,int br)
{
if(lamp||!br)return;
if(r-l+1==br)
{
for(int i=l;i<=r;i++)
{
a=ask(i);
if(a[0]+a[1]==0)
{
lamp=i+1;
break;
}
if(a[1]==0)break;
}
return;
}
int mid=(l+r)/2;
a=ask(mid);
if(a[0]+a[1]==0)
{
lamp=mid+1;
return;
}
rec(l,mid-1,a[0]);
rec(mid+1,r,a[1]);
}
int find_best(int n)
{
prec();
rec(1,n,sum);
return lamp-1;
}