#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int ans;
int m;
int N;
vector<int> query(int id){
if(id==N) return {m,0};
else{
vector<int> a=ask(id);
if(a[0]+a[1]==0) ans=id;
return a;
}
}
void solve(int l,int r,int x,int p,int q){
if(x==0) return;
if(r-l+1==x){
for(int i=l;i<=r;i++){
vector<int> a=query(i);
if(a[0]+a[1]==0){
ans=i;
return;
}
}
return;
}
int mid=(l+r)/2;
//mid+1 を聞く
vector<int> a=query(mid+1);
if(a[0]+a[1]==m){
solve(l,mid,a[0]-p,p,a[1]);
solve(mid+1,r,a[1]-q,a[0],q);
}
else{
int now=mid+1;
int cnt=1;
while(now<r){
vector<int> a=query(now+1);
if(a[0]+a[1]!=m){
cnt++;
now++;
}
else{
break;
}
}
if(now==r){
//mid+1 から r は全部特殊
solve(l,mid,x-cnt,p,q+cnt);
}
else{
vector<int> a=query(now+1);
//mid+1 から now は全部特殊
solve(l,mid,a[0]-cnt-p,p,a[1]+cnt);
solve(now+1,r,a[1]-q,a[0],q);
}
}
}
int find_best(int n) {
N=n;
if(n<=5000){
for(int i=0;i<n;i++){
vector<int> a=ask(i);
if(a[0]+a[1]==0) return i;
}
m=-1;
for(int i=0;i<30;i++){
int k=rand()%n;
vector<int> a=query(k);
if(a[0]+a[1]==0) return i;
if(m<a[0]+a[1]) m=a[0]+a[1];
}
solve(0,n-1,m,0,0);
return ans;
}
Compilation message
prize.cpp: In function 'int find_best(int)':
prize.cpp:75:1: error: expected '}' at end of input
75 | }
| ^
prize.cpp:59:22: note: to match this '{'
59 | int find_best(int n) {
| ^
prize.cpp:75:1: warning: control reaches end of non-void function [-Wreturn-type]
75 | }
| ^
