Submission #292946

#	Time	Username	Problem	Language	Result	Execution time	Memory
292946		Haunted_Cpp	The Big Prize (IOI17_prize)	C++17	20 / 100	104 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 < 400; 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 < (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) {
      if (start_location + 5 >= n) {
        ++start_location;
        continue;
      } 
      pair<int, int> few_nxt = perguntar(start_location + 5);
      if (few_nxt != cur) {
        ++start_location;
        continue;
      }
      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.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) {
      if (start_location - 5 < 0) {
         --start_location;
        continue;
      }
      pair<int, int> few_nxt = perguntar(start_location - 5);
      if (few_nxt != cur) {
         --start_location;
        continue;
      }
      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.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