oj.uz

Submission #957377

# Submission time Handle Problem Language Result Execution time Memory
957377 2024-04-03T15:13:03 Z kilkuwu The Big Prize (IOI17_prize) C++17
0 / 100
 7 ms 5912 KB 
#include "prize.h"
#include <bits/stdc++.h>

int find_best(int n) {
  std::vector<std::vector<int>> dp(n);

  auto query = [&](int i) -> std::vector<int> {
    if (dp[i].size()) return dp[i];
    return dp[i] = ask(i);
  };

  const int B = 500;
  if (n <= B) {
    for (int i = 0; i < n; i++) {
      auto res = query(i);
      if (res[0] + res[1] == 0) {
        return i;
      }
    }
    return 0;
  }

  int mx = 0;
  for (int i = 0; i < B; i++) {
    auto res = query(i);
    if (res[0] + res[1] == 0) return i;
    mx = std::max(mx, res[0] + res[1]);
  }

  int p = -1;
  for (int done = 0; done < mx; done++) {
    p++;

    int l = p;
    int r = n - 1;

    while (l < r) {
      int m = (l + r) / 2;

      auto res = query(m);

      if (res[0] + res[1] == 0) return m;

      if (res[0] + res[1] < mx || (res[0] > done)) {
        r = m;
      } else {
        l = m + 1;
      }
    }

    p = r;
  }

  return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5400 KB Output is correct
2 Correct 4 ms 5148 KB Output is correct
3 Correct 7 ms 5396 KB Output is correct
4 Incorrect 5 ms 5820 KB answer is not correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4952 KB Output is correct
2 Correct 5 ms 5912 KB Output is correct
3 Correct 4 ms 5404 KB Output is correct
4 Incorrect 3 ms 5400 KB answer is not correct
5 Halted 0 ms 0 KB -