Submission #243591

#	Time	Username	Problem	Language	Result	Execution time	Memory
243591		AlexPop28	The Big Prize (IOI17_prize)	C++11	100 / 100	65 ms	680 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"

#define dbg(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

map<int, map<int, int>> memo;

pair<int, int> Ask(int pos) {
  auto ans = ask(pos);
  return make_pair(ans[0], ans[1]);
}

int Solve(int left, int right) {
  if (left > right) {
    return -1;
  }
  
  int mid = left + (right - left) / 2;
  auto ans = Ask(mid);
  int color = ans.first + ans.second;
  memo[color][mid] = ans.first;
  
  // dbg("l = %d r = %d m = %d\n", left, right, mid);
  
  if (color == 0) {
    return mid;
  }
  
  auto it = memo[color].upper_bound(mid);
  if (it == memo[color].end() || ans.first != it->second) {
    int aux = Solve(mid + 1, right);
    if (aux != -1) return aux;
  }
  it = memo[color].lower_bound(mid);
  if (it == memo[color].begin() || ans.first != prev(it)->second) {
    int aux = Solve(left, mid - 1);
    if (aux != -1) return aux;
  }
  return -1;
}

int find_best(int n) {
  return Solve(0, n - 1);
}

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