Submission #295364

#	Time	Username	Problem	Language	Result	Execution time	Memory
295364		Haunted_Cpp	The Big Prize (IOI17_prize)	C++17	20 / 100	127 ms	15608 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5 + 5;

vector<vector<int>> dp(MAX_N);
map<int, set<int> > memo[MAX_N];
set<int> query;
 
int find_best(int n) {
  if (n == 1) {
    return 0;
  }
  pair<int, int> best_way = {-1, -1};
  auto perguntar = [&](int delta) -> pair<int, int> {
    if (dp[delta].empty()) {
      dp[delta] = ask(delta);
    }
    vector<int> res = dp[delta];
    memo[dp[delta][0]][dp[delta][1]].insert(delta);
    query.insert(delta);
    return {res[0], res[1]};
  };
  auto calc_score = [&](const pair<int, int> &res) {
    return res.first + res.second;
  };
  auto find = [&](const pair<int, int> &res) {
    const int l = res.first;
    const int r = res.second;
    if (memo[l][r].empty()) return -1;
    return *memo[l][r].rbegin();
  };
  auto rightmost = [&](int idx) -> int {
    ++idx;
    auto where = query.lower_bound(idx);
    if (where == query.end()) return 1e9;
    return *where;
  };
  for (int i = 0; i < min(n, 1); i++) {
    const int idx = i;
    pair<int, int> res = perguntar(idx);
    best_way = max(best_way, {calc_score(res), idx});
    if (calc_score(res) == 0) {
      return i;
    }
  }
  int idx = best_way.second;
  while(idx < n) {
    pair<int, int> res = perguntar(idx);
    if (res == perguntar(best_way.second)) {
      int l = idx;
      int r = n - 1;
      while(l < r) {
        const int mid = l + (r - l) / 2 + 1;
        pair<int, int> cur = perguntar(mid);
        if (res == cur) {
          l = mid;
        } else {
          r = mid - 1;
        }
      }
      idx = l + 1;
    } else {
      if (calc_score(res) == 0) {
        return idx;
      }
      ++idx;
    }
  }
  assert(1 == 2);
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:28:8: warning: variable 'find' set but not used [-Wunused-but-set-variable]
   28 |   auto find = [&](const pair<int, int> &res) {
      |        ^~~~
prize.cpp:34:8: warning: variable 'rightmost' set but not used [-Wunused-but-set-variable]
   34 |   auto rightmost = [&](int idx) -> int {
      |        ^~~~~~~~~

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