제출 #1081050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081050		juicy	The Big Prize (IOI17_prize)	C++17	100 / 100	36 ms	15532 KiB

prize

// http://ioi2017.org/tasks/editorial/prize.pdf

#include "prize.h"

#include <bits/stdc++.h>

using namespace std;

int find_best(int n) {
  vector<vector<int>> memo(n);
  auto Ask = [&](int i) {
    if (!memo[i].size()) {
      memo[i] = ask(i);
    }
  }; 
  vector<set<int>> st(n + 1);
  int res = -1;
  function<void(int, int)> dc = [&](int l, int r) {
    if (l > r || ~res) {
      return;
    }
    int md = (l + r) / 2;
    Ask(md);
    int key = memo[md][0] + memo[md][1];
    if (!key) {
      res = md;
      return;
    }
    auto it = st[key].insert(md).first;
    if (it == st[key].begin() ? memo[md][0] : memo[md][0] - memo[*prev(it)][0] > 0) {
      dc(l, md - 1);
    }
    if (~res) {
      return;
    }
    if (next(it) == st[key].end() ? memo[md][1] : memo[*next(it)][0] - memo[md][0] > 0) {
      dc(md + 1, r);
    }
  };
  dc(0, n - 1);
  return res;
}

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