Submission #292420

#	Time	Username	Problem	Language	Result	Execution time	Memory
292420		Haunted_Cpp	The Big Prize (IOI17_prize)	C++17	20 / 100	96 ms	5496 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);
}

const int MAX_N = 2e5 + 5;
bitset<MAX_N> vis;
vector<vector<int>> dp(MAX_N);

int find_best(int n) {
	vector<pair<int, int>> arr;
  auto perguntar = [&](int idx) {
    vector<int> res;
    if(vis[idx]) {
      res = dp[idx];
    } else {
      res = ask(idx);
      dp[idx] = res;
    }
    vis[idx] = 1;
    return make_pair(res[0], res[1]);
  };
  for (int i = 0; i < 350; 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 best_way = 0;
  for (auto to : arr) {
    if (to.first == 0) {
      return to.second;
    }
  }
  for (int i = 0; i < (int) arr.size(); i++) {
    if (arr[i].first == is_opt) {
      best_way = arr[i].second;
      break;
    }
  }
  int start_location; 
  // GO: START -> RIGHT
  start_location = best_way;
  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 = hi - (hi - lo) / 3;
        pair<int, int> nxt = perguntar(mid);
        if (nxt.first == 0 && nxt.second == 0) {
          return 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 = best_way;
  while(start_location >= 0) {
    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) / 3;
        pair<int, int> nxt = perguntar(mid);
        if (nxt.first == 0 && nxt.second == 0) {
          return 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: 20 / 20
• Subtask 2: 0 / 80