#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int ans;
int m;
int N;
int cnt=0;
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;
}
if(ans!=-1) 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]);
if(ans!=-1) return;
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);
if(ans!=-1) return;
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
answer is not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
answer is not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
