Submission #147494

#	Time	Username	Problem	Language	Result	Execution time	Memory
147494		RafaelSus	The Big Prize (IOI17_prize)	C++17	95.63 / 100	60 ms	504 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

int mx = -1;
int answ = -1;

int N;

int bSearch(int l, int r, int L, int R){
  l = max(l, 0);
  r = min(r, N);
  if (l >= r) return -1;
  if (L + R == mx) return -1;
  int mid = l + r >> 1;

  for (int i = mid; i < r; i++){
    vector <int> a = ask(i);
    if (a[0] + a[1] == mx){
      int x = bSearch(l, mid, L, a[1] + (mid - i));
      if (x != -1) return x;
      x = bSearch(i + 1, r, a[0], R);
      if (x != -1) return x;
      return -1;
    }else if (a[0] + a[1] == 0){
      return i;
    }
  }
  return bSearch(l, mid, L, R + (r - mid));
}


int find_best(int n){
  N = n;
  for (int i = 0; i < 500; i++){
    vector <int> a = ask(i);
    if (a[0] + a[1] == 0){
      return i;
    }
    mx = max(a[0] + a[1], mx);
  }
  return bSearch(0, n, 0, 0);
}

Compilation message (stderr)

prize.cpp: In function 'int bSearch(int, int, int, int)':
prize.cpp:16:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~

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