Submission #47720

#	Time	Username	Problem	Language	Result	Execution time	Memory
47720		SinByCos	The Big Prize (IOI17_prize)	C++14	90 / 100	79 ms	576 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
 
using namespace std;
 
const int MAXN = 2e5 + 5;
 
int find_best(int n){
  int sum = 0, p = 500;
  for(int i=0; i<min(n, 500); ++i){
    vector<int> v = ask(i);
    sum = max(sum, v[0] + v[1]);
    if(v[0] + v[1] == 0) return i;
  }
  while(p < n){
    vector<int> v = ask(p);
    if(v[0] + v[1] == 0) return p;
    int lo = p + 1, hi = n - 1, mid;
    if(v[0] + v[1] == sum){
      while(lo <= hi){
        mid = (lo + hi)/2;
        vector<int> ans = ask(mid);
        if(ans[0] + ans[1] == 0) return mid;
        if(lo == hi) break;
        if(ans[0] + ans[1] < sum) hi = mid;
        else if (ans[0]+ans[1] > sum) assert(false);
        else{
          if(v[1] - ans[1] > 0) hi = mid - 1;
          else lo = mid + 1;
        }
      }
      p = lo + 1;
    }
		else p++;
  }
}

Compilation message (stderr)

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

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