Submission #288370

#	Time	Username	Problem	Language	Result	Execution time	Memory
288370		davi_bart	The Big Prize (IOI17_prize)	C++14	20 / 100	113 ms	500 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;
  vector<int>p;
  for(int i=0;i<450;i++){
    auto res=ask(i);
    ma=max(ma,res[0]+res[1]);
    if(res[0]+res[1]==0)return i;
    p.push_back(res[0]+res[1]);
  }
  int presi=0;
  for(int i=0;i<p.size();i++){
    if(p[i]<ma)presi++;
  }
  int pos=449;
  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;
      if(res[0]+res[1]==ma)break;
      pos++;
      presi++;
    }
  }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i=0;i<p.size();i++){
      |               ~^~~~~~~~~
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: 0 / 80