Submission #1041251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041251		PCTprobability	커다란 상품 (IOI17_prize)	C++17	Compilation error	0 ms	0 KiB

prize

#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 (stderr)

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 | }
      | ^