Submission #292410

#	Time	Username	Problem	Language	Result	Execution time	Memory
292410		Haunted_Cpp	The Big Prize (IOI17_prize)	C++17	0 / 100	2 ms	384 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int gerar(int lo, int hi) {
  return uniform_int_distribution<int>(lo, hi) (rng);
}

int find_best(int n) {
	vector<pair<int, int>> arr;
  auto perguntar = [&](int idx) {
    vector<int> res;
    res = ask(idx);
    return make_pair(res[0], res[1]);
  };
  for (int i = 0; i < 100; i++) {
    const int where = gerar(0, n - 1);
    pair<int, int> res = perguntar(where);
    arr.emplace_back(res.first + res.second, where);
  }
  shuffle(arr.begin(), arr.end(), rng);
  
  int is_opt = (*max_element(arr.begin(), arr.end())).first;
  int start_location; 
  // GO: START -> RIGHT
  start_location = (*max_element(arr.begin(), arr.end())).second;
  while(start_location != n) {
    pair<int, int> cur = perguntar(start_location);
    int s = cur.first + cur.second;
    if (s == is_opt) {
      int lo = start_location;
      int hi = n - 1;
      while(lo < hi) {
        const int mid = lo + (hi - lo) / 2 + 1;
        pair<int, int> nxt = perguntar(mid);
        if (nxt != cur) {
          hi = mid - 1;
        } else {
          lo = mid;
        } 
      }
      start_location = lo + 1;
    } else {
      if (s == 0) {
        return start_location;
      }
      ++start_location;
    }
  }
  // GO: START -> LEFT
  start_location = arr[0].second;
  while(start_location != n) {
    pair<int, int> cur = perguntar(start_location);
    int s = cur.first + cur.second;
    if (s == is_opt) {
      int lo = 0;
      int hi = start_location;
      while(lo < hi) {
        const int mid = lo + (hi - lo) / 2;
        pair<int, int> nxt = perguntar(mid);
        if (nxt == cur) {
          hi = mid;
        } else {
          lo = mid + 1;
        } 
      }
      start_location = hi - 1;
    } else {
      if (s == 0) {
        return start_location;
      }
      --start_location;
    }
  }
  assert(0 == 1);
}

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