Submission #295433

#	Time	Username	Problem	Language	Result	Execution time	Memory
295433		Haunted_Cpp	The Big Prize (IOI17_prize)	C++17	20 / 100	104 ms	14496 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) {
    //~ if (dp[delta].empty()) {
      //~ dp[delta] = ask(delta);
    //~ }
    vector<int> res = ask(delta); // dp[delta];
    //~ memo[dp[delta][0]][dp[delta][1]].insert(delta);
    //~ query.insert(delta);
    return make_pair(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;
  //~ };
  int mx = 0;
  for (int i = 0; i < min(n, 1000); i++) {
    pair<int, int> res = perguntar(i);
    mx = max(mx, calc_score(res));
    //~ best_way = max(best_way, {calc_score(res), i});
    if (calc_score(res) == 0) {
      return i;
    }
  }
  
  int idx = -1;
  for (int i = 0; i < min(n, 1000); i++) {
    pair<int, int> res = perguntar(i);
    if (calc_score(res) == mx) {
      idx = i;
      break;
    }
  }
  
  int start_location = idx;
  
  while(idx < n) {
    pair<int, int> res = perguntar(idx);
    //~ cout << res.first << ' ' <<  res.second << '\n';
    //~ cout << perguntar(best_way.second).first << ' ' << perguntar(best_way.second).second << '\n';
    if (res == perguntar(start_location)) {
      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 (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;
    }
  }
  assert(1 == 2);
}

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