Submission #295527

#	Time	Username	Problem	Language	Result	Execution time	Memory
295527		Haunted_Cpp	The Big Prize (IOI17_prize)	C++17	96.70 / 100	83 ms	15228 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) {
  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, 475); 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;
    }
  }
  const int BLOCK = 2 * sqrt(n);
  for (int i = 0; i < n; i++) {
    if (i * BLOCK > n) break;
    perguntar(i * BLOCK);
  }
  const int start_location = best_way.second;
  int idx = start_location;
  while(idx < n) {
    pair<int, int> res = perguntar(idx);
    if (calc_score(res) == calc_score(perguntar(start_location))) {
      int l = max(idx, find(res));
      int r = min(n - 1, rightmost(l)) - 1;
      while(l < r) {
        const int mid = l + (r - l) / 2 + 1;
        pair<int, int> cur = perguntar(mid);
        if (calc_score(cur) == 0) {
          return mid;
        }
        if (res == cur) {
          l = mid;
        } else {
          r = mid - 1;
        }
      }
      idx = l + 1;
    } else {
      if (calc_score(res) == 0) {
        return idx;
      }
      ++idx;
    }
  }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
   77 | }
      | ^

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