Submission #957398

#	Time	Username	Problem	Language	Result	Execution time	Memory
957398		kilkuwu	The Big Prize (IOI17_prize)	C++17	100 / 100	35 ms	16236 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);
  };

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

  int answer = -1;

  std::vector<std::set<int>> mp(n);

  auto go = [&](auto self, int l, int r) -> void {
    if (l > r) return;
    if (answer >= 0) return;

    int m = (l + r) / 2;
    auto res = query(m);
    auto rnk = res[0] + res[1];

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

    auto it = mp[rnk].insert(m).first;

    if (it == mp[rnk].begin()) {
      if (res[0]) self(self, l, m - 1);
    } else {
      auto r1 = query(*std::prev(it));
      if (res[0] - r1[0] > 0) {
        self(self, l, m - 1);
      }
    }

    if (answer >= 0) return;

    it = mp[rnk].find(m);

    if (it == --mp[rnk].end()) {
      if (res[1]) self(self, m + 1, r);
    } else {
      auto r2 = query(*std::next(it));
      if (r2[0] - res[0] > 0) {
        self(self, m + 1, r);
      }
    }
  };

  go(go, 0, n - 1);

  return answer;
}

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