Submission #335666

#	Time	Username	Problem	Language	Result	Execution time	Memory
335666		couplefire	The Big Prize (IOI17_prize)	C++17	20 / 100	58 ms	492 KiB

prize

#include "prize.h"
#include <cstdlib>

int recursive_find_best(int n, int m, int s, int e, int xl, int xr) {
  std::vector<int> r, r0;
  if (xl + xr >= m) return -1;
  if (e - s < 2) {
    for (int i = s; i <= e; ++i) {
      r = ask(i);
      if (r[0] + r[1] == 0) return i;
    }
    return -1;
  }
  int midl = (s + e) / 2, midr = (s + e) / 2;
  r0 = ask(midl);
  if (r0[0] + r0[1] == 0) return midl;
  for (r = r0, --midl; r[0] + r[1] < m && midl > s; --midl) {
    r = ask(midl);
    if (r[0] + r[1] == 0) return midl;
  }
  int ans = recursive_find_best(n, m, s, midl, xl, r[1]);
  if (ans >= 0) return ans;
  for (r = r0, ++midr; r[0] + r[1] < m && midr < e; ++midr) {
    r = ask(midr);
    if (r[0] + r[1] == 0) return midr;
  }
  return recursive_find_best(n, m, midr, e, r[0], xr);
}
			
int find_best(int n) {
  int m = 0;
  for (int i = 0; i < 250; ++i) {
    std::vector<int> r = ask(std::rand() % n);
    if (r[0] + r[1] > m) m = r[0] + r[1];
  }
  return recursive_find_best(n, m, 0, n - 1, 0, 0);
}

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