Submission #288371

#	Time	Username	Problem	Language	Result	Execution time	Memory
288371		davi_bart	The Big Prize (IOI17_prize)	C++14	90 / 100	109 ms	512 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ld long double
vector<int> ask(int i);
int solve(int n){
  for(int i=0;i<n;i++){
    auto res=ask(i);
    if(res[0]+res[1]==0)return i;
  }
}
int find_best(int n){
  if(n<=5000)return solve(n);
  int ma=0;
  for(int i=0;i<500;i++){
    auto res=ask(i);
    ma=max(ma,res[0]+res[1]);
    if(res[0]+res[1]==0)return i;
  }
  int presi=0;
  int pos=-1;
  while(1){
    int q=20;
    while(q>=0){
      if((1<<q)+pos>=n){
        q--;
        continue;
      }
      auto res=ask(pos+(1<<q));
      if(res[0]==presi && res[0]+res[1]==ma)pos+=(1<<q);
      q--;
    }
    while(1){
      auto res=ask(pos+1);
      if(res[0]==0 && res[1]==0)return pos+1;
      pos++;
      if(res[0]+res[1]==ma)break;
      presi++;
    }
  }
}

Compilation message (stderr)

prize.cpp: In function 'int solve(int)':
prize.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
   14 | }
      | ^

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