Submission #418008

#	Time	Username	Problem	Language	Result	Execution time	Memory
418008		Hegdahl	The Big Prize (IOI17_prize)	C++17	90 / 100	110 ms	2160 KiB

prize

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

map<int, set<int>> where;
map<int, ar<int, 2>> mem;
ar<int, 2> qry(int i) {
  auto it = mem.find(i);
  if (it != mem.end()) return it->second;
  auto v = ask(i);
  int l = v[0], r = v[1];
  where[l+r].insert(i);
  return mem.insert({i, {l, r}}).first->second;
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int find_best(int n) {

  vector<int> idxs(n);
  iota(idxs.begin(), idxs.end(), 0);
  shuffle(idxs.begin(), idxs.end(), rng);

  for (int rep = 0; rep < min(500, n); ++rep)
    qry(idxs[rep]);

  /*
  for (auto &&[s, idxs] : where) {
    cerr << s << ": ";
    for (int i : idxs)
      cerr << i << ' ';
    cerr << '\n';
  } // */

  int worst = where.rbegin()->first;

  vector<ar<int, 2>> bad_ranges;

  auto is_bad = [&](int i) {
    auto [l, r] = qry(i);
    return l+r == worst;
  };

  int i = 0;
  while (true) {
    while (i < n && !is_bad(i)) ++i;
    if (i == n) break;

    auto p = qry(i);

    int lo = i, hi = n-1;
    while (lo != hi) {
      int ce = lo + (hi-lo+1)/2;
      if (qry(ce) == p) lo = ce;
      else hi = ce-1;
    }

    bad_ranges.push_back({i, lo});
    i = lo+1;
  }

  return *where[0].begin();
}

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