Submission #316105

#	Time	Username	Problem	Language	Result	Execution time	Memory
316105		MrDomino	The Big Prize (IOI17_prize)	C++14	0 / 100	3051 ms	67144 KiB

prize

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

using namespace std;

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

map<int, vector<int>> ret;

vector<int> get(int pos) {
  if (ret.count(pos)) {
    return ret[pos];
  } else {
    vector<int> v = ask(pos);
    ret[pos] = v;
    return v;
  }
}

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

int rep(int l, int r) {
  if (l > r) {
    return 0;
  }
  int m = (l + r) / 2;
  vector<int> v = get(m);
  if (v[0] == 0 && v[1] == 0) {
    return m;
  }
  if (v[0] == 0) {
    return rep(m + 1, r);
  }
  if (v[1] == 0) {
    return rep(l, m - 1);
  }
  if (v[0] > v[1]) {
    int x = rep(l, m - 1);
    if (x) {
      return x;
    } else {
      return rep(m + 1, r);
    }
  } else {
    int x = rep(m + 1, r);
    if (x) {
      return x;
    } else {
      return rep(l, m - 1);
    }
  }
}

int find_best(int n) {
  vector<int> bucket(n);
  int r = sqrt(n);
  for (int i = 0; i < n; i++) {
    bucket[i] = i / r;
  }
  vector<pair<int, int>> buckets;
  int l = 0;
  while (l < n) {
    int r = l;
    while (r + 1 < n && bucket[l] == bucket[r + 1]) {
      r++;
    }
    buckets.push_back({l, r});
    r = l + 1;
  }
  shuffle(buckets.begin(), buckets.end(), rng);
  for (auto &it : buckets) {
    int l = it.first;
    int r = it.second;
    if (get(l) != get(r)) {
      int x = rep(l, r);
      if (x) {
        return x;
      }
    }
  }
  assert(0);
}

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