Submission #1175459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175459		mannshah1211	The Big Prize (IOI17_prize)	C++20	20 / 100	30 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));
  auto uwu = [&](int i) {
    if (cache[i] != vector<int>(2, -1)) {
      return cache[i];
    }
    return cache[i] = ask(i);
  };
  int mx = 0, ptr = 0;
  while (ptr < n) {
    vector<int> v = uwu(ptr);
    if (v[0] + v[1] == 0) {
      return ptr;
    }
    if (v[0] == ptr) {
      mx = v[0] + v[1];
      break;
    }
    ptr++;
  }
  while (ptr < n) {
    vector<int> v1 = uwu(ptr);
    if (v1[0] + v1[1] == mx) {
      int low = ptr + 1, high = n - 1, idx = -1;
      while (low <= high) {
        int mid = (low + high) >> 1;
        vector<int> v2 = uwu(mid);
        if (v2[1] == v1[1]) {
          low = mid + 1;
        } else {
          idx = mid;
          high = mid - 1;
        }
      }
      assert(idx != -1);
      ptr = idx;
    } else {
      if (v1[0] + v1[1] == 0) {
        return ptr;
      }
      ptr += 1;
    }
  }
  assert(false);
}

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