Submission #99217

#	Time	Username	Problem	Language	Result	Execution time	Memory
99217		eriksuenderhauf	The Big Prize (IOI17_prize)	C++11	97.64 / 100	51 ms	5396 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
#define pii pair<int,innt>
#define vi vector<int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 50;
vi ans[MAXN];
int cur = 0;
int ret = -1;

void solve(int l, int r) {
 if (r - l < 2 || ret != -1)
  return;
 if (ans[l][1] == ans[r][1])
  return;
 int m = (l + r) / 2;
 ans[m] = ask(m);
 if (ans[m][0] + ans[m][1] == 0) {
  ret = m;
  return;
 }
 if (ans[m][0] + ans[m][1] != cur) {
  solve(l, m);
  solve(m, r);
  return;
 }
 if (ans[l][0] == ans[m][0] && ans[m][0] == ans[r][0])
  return;
 if (ans[l][0] == ans[m][0])
  solve(m, r);
 else if (ans[l][0] == ans[m][0])
  solve(l, m);
 else {
  solve(l, m);
  if (ret != -1)
   return;
  solve(m, r);
 }
}

int find_best(int n) {
 int val = 454;
 for (int i = 0; i < min(n,455); i++) {
  ans[i] = ask(i);
  if (ans[i][0] + ans[i][1] == 0)
   return i;
  cur = max(cur, ans[i][0] + ans[i][1]);
  if (cur > 100) {
   val = i;
   break;
  }
 }
 if (val < n - 1)
  ans[n-1] = ask(n-1);
 if (ans[n-1][0] + ans[n-1][1] == 0)
  return n-1;
 solve(val,n-1);
 return ret;
}

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