Submission #137875

#	Time	Username	Problem	Language	Result	Execution time	Memory
137875		MAMBA	커다란 상품 (IOI17_prize)	C++17	20 / 100	55 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;
}

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;
  rep(i, mid, r) {
    vi me = gholi(i);
    if (sum(me) == 0) return mid;
    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) {
  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:39:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~

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