Submission #361570

#	Time	Username	Problem	Language	Result	Execution time	Memory
361570		KoD	The Big Prize (IOI17_prize)	C++17	100 / 100	58 ms	1512 KiB

prize

#include "prize.h"
#include <map>
#include <set>
#include <vector>

std::map<int, std::set<int>> trace;
std::vector<int> left;

int dfs(const int l, const int r) {
  if (l > r) {
    return -1;
  }
  const auto m = (l + r) / 2;
  const auto get = ask(m);
  left[m] = get[0];
  const auto sum = get[0] + get[1];
  if (sum == 0) {
    return m;
  }
  auto itr = trace[sum].insert(m).first;
  if (itr == trace[sum].begin() || left[*std::prev(itr)] != left[m]) {
    const auto tmp = dfs(l, m - 1);
    if (tmp != -1) {
      return tmp;
    }
  }
  if (std::next(itr) == trace[sum].end() || left[*std::next(itr)] != left[m]) {
    const auto tmp = dfs(m + 1, r);
    if (tmp != -1) {
      return tmp;
    }
  }
  return -1;
}

int find_best(int n) {
  left.resize(n);
  return dfs(0, n - 1);
}

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