Submission #137893

#	Time	Username	Problem	Language	Result	Execution time	Memory
137893		MAMBA	The Big Prize (IOI17_prize)	C++17	97.92 / 100	69 ms	960 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];
  mp[v] = ask(v);
  smax(mx, sum(mp[v]));
  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;
  int l2 = mid, r2 = mid, pos = mid;
  rep(i, 0, r - l) {
    mid += (i & 1) ? -i : i;
    smin(l, mid);
    smax(r, mid);
    pos = mid;
    vi me = gholi(mid);
    if (sum(me) == 0) return mid;
    if (sum(me) == mx) break;
  }

  if (r2 - l2 + le + ri == mx) return -1;
  int res = solve(l, l2, le, pos - l2 + gholi(pos)[1]);
  if (~res) return res;
  return solve(r2 + 1, r, r2 - pos + gholi(pos)[0], ri);
}

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

  return solve(0, n, 0, 0);
}

Compilation message (stderr)

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

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