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 <iostream>
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include "prize.h"
using namespace std;
int all[200005];
int l[200005],r[200005];
int ans=0;
int F(int L,int R)
{
//printf("%d %d\n",L,R);
vector < int > t;
int x;
if(l[(L+R)/2]==-1)
{
ans++;
assert(ans<=10000);
t=ask((L+R)/2);
l[(L+R)/2]=t[0];
r[(L+R)/2]=t[1];
}
if(l[R]==-1)
{
ans++;
assert(ans<=10000);
t=ask(R);
l[R]=t[0];
r[R]=t[1];
}
if(l[L]==-1)
{
ans++;
assert(ans<=10000);
t=ask(L);
l[L]=t[0];
r[L]=t[1];
}
if(l[L]==0&&r[L]==0) return L;
if(l[R]==0&&r[R]==0) return R;
if(l[(L+R)/2]==0&&r[(L+R)/2]==0) return (L+R)/2;
if(L==R)
{
if(l[L]||r[L]) return -1;
return L;
}
else if(L+1==R)
{
if(l[L]||r[L])
{
if(l[R]||r[R]) return -1;
return R;
}
return L;
}
else
{
//printf("%d %d %d %d %d %d\n",l[L],r[L],l[(L+R)/2],r)
if(r[R]==r[(L+R)/2]) return F(L,(L+R)/2);
else if(l[L]==l[(L+R)/2]) return F((L+R)/2+1,R);
else
{
x=F((L+R)/2+1,R);
if(x!=-1) return x;
return F(L,(L+R)/2);
}
}
}
int find_best(int n)
{
vector < int > t;
int i,j,all=0;
for(i=0;i<n;i++) l[i]=r[i]=-1;
ans++;
assert(ans<=10000);
t=ask(0);
l[0]=t[0];
r[0]=t[1];
ans++;
assert(ans<=10000);
t=ask(n-1);
l[n-1]=t[0];
r[n-1]=t[1];
return F(0,n-1);
}
Compilation message (stderr)
prize.cpp: In function 'int find_best(int)':
prize.cpp:75:11: warning: unused variable 'j' [-Wunused-variable]
int i,j,all=0;
^
prize.cpp:75:13: warning: unused variable 'all' [-Wunused-variable]
int i,j,all=0;
^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |