Submission #292411

#	Time	Username	Problem	Language	Result	Execution time	Memory
292411		Haunted_Cpp	The Big Prize (IOI17_prize)	C++17	20 / 100	108 ms	392 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 < 75; 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 (int i = 0; i < 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 = 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 = 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 = 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);
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int i = 0; i < arr.size(); i++) {
      |                   ~~^~~~~~~~~~~~

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