Submission #316114

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

prize

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

using namespace std;

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

const int N = 200000 + 7;
vector<int> ret[N];
int sol;

vector<int> get(int pos) {
  if (ret[pos].empty()) {
    ret[pos] = ask(pos);
  }
  if (ret[pos][0] == 0 && ret[pos][1] == 0) {
    sol = pos;
  }
  return ret[pos];
}

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) {
  sol = -1;
  vector<int> bucket(n);
  int r = 50;
  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});
    l = r + 1;
  }
  shuffle(buckets.begin(), buckets.end(), rng);
  for (auto &it : buckets) {
    int l = it.first;
    int r = it.second;
    vector<int> vl = get(l);
    vector<int> vr = get(r);
    if (sol != -1) {
      return sol;
    }
    if (vl != vr) {
      int x = rep(l, r);
      if (x) {
        return x;
      }
    }
  }
  while (1) {

  }
}

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