Submission #208873

#	Time	Username	Problem	Language	Result	Execution time	Memory
208873		rama_pang	The Big Prize (IOI17_prize)	C++14	100 / 100	58 ms	836 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>
using namespace std;

map<int, pair<int, int>> memo;
vector<int> query(int i) {
  vector<int> res;
  if (memo.count(i)) {
    res.emplace_back(memo[i].first);
    res.emplace_back(memo[i].second);
  } else {
    res = ask(i);
    memo[i] = {res[0], res[1]};
  }
  return res;
}

int numValuable;
vector<int> candidates; // non-lollipop boxes

void binarySearch(int leftValuable, int rightValuable, int left, int right) {
  if (left > right || leftValuable + rightValuable == numValuable) {
    return;
  }

  int mid = (left + right) / 2;
  vector<int> res = query(mid);
  
  if (res[0] + res[1] == numValuable) { // mid is a lollipop box
    binarySearch(leftValuable, res[1], left, mid - 1);
    binarySearch(res[0], rightValuable, mid + 1, right);
  } else { // mid is a non-lollipop box
    candidates.emplace_back(mid);
    int nearestLeft, nearestRight;

    for (int i = mid + 1; i <= right; i++) {
      res = query(i);
      if (res[0] + res[1] == numValuable) {
        nearestRight = i;
        binarySearch(query(nearestRight)[0], rightValuable, nearestRight + 1, right);
        break;
      } else { // i is a non-lollipop box
        candidates.emplace_back(i);
      }
    }

    for (int i = mid - 1; i >= left; i--) {
      res = query(i);
      if (res[0] + res[1] == numValuable) {
        nearestLeft = i;
        binarySearch(leftValuable, query(nearestLeft)[1], left, nearestLeft - 1);
        break;
      } else { // i is a non-lollipop box
        candidates.emplace_back(i);
      }
    }
  }
}

int find_best(int n) {
  numValuable = 0;
  for (int i = 0; i < min(n, 500); i++) { // least valuable box must satisfy sum^2 <= n, and since n <= 200000 then sum <= 500 will suffice
    vector<int> res = query(i);
    if (res[0] + res[1] > numValuable) {
      numValuable = res[0] + res[1];
    } 
    if (numValuable > 30) { // second least valuable box must satisfy (sum^2)^2 <= n, and since n <= 200000 then sum <= 30 will suffice
      break; // we will only check at most one least valuable box, the rest will be valuable and checked later anyways
    }
  }

  binarySearch(0, 0, 0, n - 1);

  int ans = -1;
  for (auto &c : candidates) {
    vector<int> res = query(c);
    if (res[0] == 0 && res[1] == 0) {
      ans = c;
    }
  }

  return ans;
}

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