Submission #316078

#	Time	Username	Problem	Language	Result	Execution time	Memory
316078		MrDomino	The Big Prize (IOI17_prize)	C++14	20 / 100	84 ms	376 KiB

prize

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

using namespace std;

mt19937 rng((long long) (new char));



int rep(int l, int r) {
  if (l > r) {
    return 0;
  }
  int m = l + rng() % (r - l + 1);
  vector<int> v = ask(m);
  if (v[0] == 0 && v[1] == 0) {
    return m;
  }
  int x = rep(l, m - 1);
  if (x) {
    return x;
  }
  int lo = m + 1, hi = r, last = m;
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    vector<int> v2 = ask(mid);
    if (v == v2) {
      last = mid;
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return rep(last + 1, r);
}

int find_best(int n) {
  return rep(0, n - 1);
}

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