Submission #137885

#	Time	Username	Problem	Language	Result	Execution time	Memory
137885		MAMBA	The Big Prize (IOI17_prize)	C++17	20 / 100	3045 ms	896 KiB

prize

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

using namespace std;

#define rep(i, j, k) for (int i = j; i < (int)k; i++)

typedef vector<int> vi;

inline bool smax(int &a, int b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

inline bool smin(int &a, int b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}

inline int sum(vi me) { return me[0] + me[1]; }

int mx;
map<int, vi> mp;
inline vi gholi(int v) {
  if (mp.count(v)) return mp[v];
  assert(mp.size() + 1 <= 10000);
  mp[v] = ask(v);
  while (mp.size() > 450 && !(sum(mp[v]) <= mx))
    ;
  return mp[v];
}

int N;

int solve(int l, int r, int le, int ri) {
  assert(l >= 0 && r <= N);
  if (l >= r || le + ri == mx) return -1;
  int mid = l + r >> 1;
  rep(i, mid, r) {
    vi me = gholi(i);
    if (sum(me) == 0) return i;
    if (sum(me) == mx) {
      int res = solve(l, mid, le, me[1] + (i - mid));
      if (~res) return res;
      return solve(i + 1, r, me[0], ri);
    }
  }
  return solve(l, mid, le, r - mid + ri);
}

int find_best(int n) {
  N = n;
  mp.clear();
  mx = -1;
  rep(i, 0, min(n, 450)) smax(mx, sum(gholi(i)));

  int me = solve(0, n, 0, 0);
  assert(~me);
  return me;
}

Compilation message (stderr)

prize.cpp: In function 'int solve(int, int, int, int)':
prize.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~

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