Submission #137869

#	Time	Username	Problem	Language	Result	Execution time	Memory
137869		MAMBA	The Big Prize (IOI17_prize)	C++17	20 / 100	117 ms	2660 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;
}

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

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

int mx;

int solve(int l, int r, int le, int ri) {
  if (l >= r || le + ri == mx) return -1;
  int mid = l + r >> 1;
  int l2 = mid, r2 = mid, pos = mid;
  while (mid < r) {
    smin(l2, mid);
    smax(r2, mid);
    pos = mid;
    vi me = gholi(mid);
    if (sum(me) == 0) return mid;
    if (sum(me) == mx) break;
    mid++;
  }
  if (mid == r) return solve(l, l2, le, ri + r - mid);
  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;
  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:39:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~

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