Submission #295452

#	Time	Username	Problem	Language	Result	Execution time	Memory
295452		Haunted_Cpp	The Big Prize (IOI17_prize)	C++17	90 / 100	140 ms	15532 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, 500); 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 start_location = best_way.second;
  while(start_location < n) {
    pair<int, int> cur = perguntar(start_location);
    int s = cur.first + cur.second;
    if (s == best_way.first) {
      //~ if (start_location + 10 >= n) {
        //~ ++start_location;
        //~ continue;
      //~ } 
      //~ pair<int, int> few_nxt = perguntar(start_location + 10);
      //~ if (few_nxt != cur) {
        //~ ++start_location;
        //~ continue;
      //~ }
      int lo = start_location;
      int hi = n - 1;
      while(lo < hi) {
        const int mid = lo + (hi - lo) / 2 + 1;
        pair<int, int> nxt = perguntar(mid);
        if (nxt.first == 0 && nxt.second == 0) {
          return mid;
        }
        if (nxt != cur) {
          hi = mid - 1;
        } else {
          lo = mid;
        } 
      }
      start_location = lo + 1;
    } else {
      if (s == 0) {
        return start_location;
      }
      ++start_location;
    }
  }
  
  
  
  
  return -1;
}

Compilation message (stderr)

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

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