Submission #243584

#	Time	Username	Problem	Language	Result	Execution time	Memory
243584		AlexPop28	The Big Prize (IOI17_prize)	C++11	0 / 100	5 ms	384 KiB

prize

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

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) {
  int mid = left + (right - left) / 2;
  auto ans = Ask(mid);
  int color = ans.first + ans.second;
  memo[color][mid] = ans.first;
  
  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;
  if (it == memo[color].begin() || ans.first != prev(it)->second) {
    int aux = Solve(left, mid);
    if (aux != -1) return aux;
  }
  return -1;
}

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

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