Submission #1175492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175492		mannshah1211	The Big Prize (IOI17_prize)	C++20	90 / 100	29 ms	11368 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

int find_best(int n) {
  vector<vector<int>> cache(n, vector<int>(2, -1));
  int queries = 0;
  auto uwu = [&](int i) {
    if (cache[i] != vector<int>(2, -1)) {
      return cache[i];
    }
    queries++;
    assert(queries < 10000);
    return cache[i] = ask(i);
  };
  int mx = 0, ptr = 0;
  for (int i = 0; i < min(480, n); i++) {
    vector<int> v = uwu(i);
    if (v[0] + v[1] > mx) {
      mx = v[0] + v[1];
      ptr = i;
    }
    if (v[0] + v[1] == 0) {
      return i;
    }
  }
  while (ptr < n) {
    vector<int> v1 = uwu(ptr);
    if (v1[0] + v1[1] == mx) {
      int low = ptr, high = n - 1, idx = -1;
      while (low <= high) {
        int mid = (low + high) >> 1;
        vector<int> v2 = uwu(mid);
        if (v2[1] == v1[1]) {
          idx = mid;
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }
      ptr = idx + 1;
    } else {
      if (v1[0] + v1[1] == 0) {
        return ptr;
      }
      ptr += 1;
    }
  }
  return -1;
}

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