Submission #316080

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

prize

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

using namespace std;

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

int rn(int l, int r) {
  return l + rng() % (r - l + 1);
}

int rep(int l, int r) {
  if (l > r) {
    return 0;
  }
  if (l == r) {
    vector<int> v = ask(l);
    if (v[0] == 0 && v[1] == 0) {
      return l;
    } else {
      return 0;
    }
  }
  int i = rn(l, r), j = rn(l, r);
  while (i == j) {
    j = rn(l, r);
  }
  if (i > j) {
    swap(i, j);
  }
  vector<int> v_i = ask(i);
  if (v_i[0] == 0 && v_i[1] == 0) return i;
  vector<int> v_j = ask(j);
  if (v_j[0] == 0 && v_j[1] == 0) return j;
  vector<pair<int, int>> seg;
  if (v_i == v_j) {
    if (v_i[0] > 0) seg.push_back({l, i - 1});
    if (v_j[1] > 0) seg.push_back({i + 1, r});
  } else {
    if (v_i[0] > 0) seg.push_back({l, i - 1});
    if (v_i[0] != v_j[0] || 1) seg.push_back({l + 1, r - 1});
    if (v_j[1] > 0) seg.push_back({i + 1, r});
  }
  shuffle(seg.begin(), seg.end(), rng);
  for (auto &it : seg) {
    int x = rep(it.first, it.second);
    if (x) {
      return x;
    }
  }
  return 0;
}

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

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