Submission #316115

#	Time	Username	Problem	Language	Result	Execution time	Memory
316115		MrDomino	The Big Prize (IOI17_prize)	C++14	20 / 100	86 ms	384 KiB

prize

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

using namespace std;

mt19937 rng((long long) (new char));

int rn(int l, int r) {
  return l + rng() % (r - l + 1);
}

int rep(int l, int r, int q) {
  assert(q >= 0);
  if (l > r || q == 0) {
    return 0;
  }
  int m = (l + r) / 2;
  int p1 = max(l, m - 5);
  int p2 = min(r, m + 5);
  if (q == 0) {
    return 0;
  }
  q--;
  vector<int> aprox = ask(m);
  if (aprox[0] == 0 && aprox[1] == 0) {
    return m;
  }
  for (int j = p1; j <= p2; j++) {
    if (j != m) {
      if (q == 0) {
        return 0;
      }
      q--;
      vector<int> v = ask(j);
      if (v[0] == 0 && v[1] == 0) {
        return j;
      }
      aprox[0] = min(aprox[0], v[0]);
      aprox[1] = min(aprox[1], v[1]);
    }
  }
  if (aprox[0] == 0) {
    return rep(p2 + 1, r, q);
  }
  if (aprox[1] == 0) {
    return rep(l, p1 - 1, q);
  }
  int c0 = (long long) aprox[0] * q / (aprox[0] + aprox[1]);
  int c1 = q - c0;
  int x = rep(l, p1 - 1, c0);
  if (x) {
    return x;
  } else {
    return rep(p2 + 1, r, c1);
  }
}

int find_best(int n) {
  return rep(0, n - 1, 9000 + 1000 - 8);
}

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