제출 #292921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292921		Haunted_Cpp	커다란 상품 (IOI17_prize)	C++17	20 / 100	98 ms	416 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 < 500; 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) {
      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;
      }
      int t = 5;
      while(t--) {
        ++start_location;
        if (start_location > n) break;
        cur = perguntar(start_location);
        s = cur.first + cur.second;
        if (s == is_opt) {
          continue;
        }
        if (s == 0) {
          return 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) / 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;
      }
      int t = 5;
      while(t--) {
        --start_location;
        if (start_location < 0) return 0;
        cur = perguntar(start_location);
        s = cur.first + cur.second;
        if (s == is_opt) {
          continue;
        }
        if (s == 0) {
          return start_location;
        }
      }
    }
  }
  assert(0 == 1);
}

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