Submission #418023

#	Time	Username	Problem	Language	Result	Execution time	Memory
418023		Hegdahl	The Big Prize (IOI17_prize)	C++17	100 / 100	59 ms	1780 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;
map<int, map<int, int>> rightmost;
map<int, map<int, int>> leftmost;
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);

  if (!rightmost[l+r].count(l)) rightmost[l+r][l] = i;
  else rightmost[l+r][l] = max(rightmost[l+r][l], i);

  if (!leftmost[l+r].count(l)) leftmost[l+r][l] = i;
  else leftmost[l+r][l] = min(leftmost[l+r][l], 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);

  int need = sqrt(2e5)+1; // since adaptive it needs to be 100% probability of correct

  for (int rep = 0; rep < need; ++rep)
    qry(idxs[rep*n/need]);

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

  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);
    auto [l, r] = p;

    auto rmit = rightmost[l+r].find(l);
    auto lmit = leftmost[l+r].upper_bound(l);

    int lo = rmit->second, hi;

    if (lmit == leftmost[l+r].end()) hi = n-1;
    else hi = lmit->second;

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

    i = lo+1;
  }

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

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