Submission #957378

#	Time	Username	Problem	Language	Result	Execution time	Memory
957378		kilkuwu	The Big Prize (IOI17_prize)	C++17	90 / 100	49 ms	6544 KiB

prize

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

int find_best(int n) {
  std::vector<std::vector<int>> dp(n);

  auto query = [&](int i) -> std::vector<int> {
    if (dp[i].size()) return dp[i];
    return dp[i] = ask(i);
  };

  const int B = 500;
  if (n <= B) {
    for (int i = 0; i < n; i++) {
      auto res = query(i);
      if (res[0] + res[1] == 0) {
        return i;
      }
    }
    return 0;
  }

  int mx = 0;
  for (int i = 0; i < B; i++) {
    auto res = query(i);
    if (res[0] + res[1] == 0) return i;
    mx = std::max(mx, res[0] + res[1]);
  }

  int p = -1;
  for (int done = 0; done < mx; done++) {
    p++;

    int l = p;
    int r = n - 1;

    while (l < r) {
      int m = (l + r) / 2;

      auto res = query(m);

      if (res[0] + res[1] == 0) return m;

      if (res[0] + res[1] < mx || (res[0] > done)) {
        r = m;
      } else {
        l = m + 1;
      }
    }

    p = r;
    auto res = query(p);
    if (res[0] + res[1] == 0) return p;
  }

  return 0;
}

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