Submission #1041286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041286		PCTprobability	The Big Prize (IOI17_prize)	C++17	100 / 100	26 ms	600 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int ans=-1;
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(now+1,r,a[1]-q,a[0],q);
      if(ans!=-1) return;
      solve(l,mid,a[0]-cnt-p,p,a[1]+cnt);
      if(ans!=-1) return;
    }
  }
}
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<500;i++){
    int k=i%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];
    if(m>=40) break;
  }
  solve(0,n-1,m,0,0);
  return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80