Submission #886910

#	Time	Username	Problem	Language	Result	Execution time	Memory
886910		Zero_OP	Rice Hub (IOI11_ricehub)	C++14	100 / 100	21 ms	3676 KiB

ricehub

#include<bits/stdc++.h>

using namespace std;

#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))

template<class T> bool minimize(T& a, T b){
  if(a > b) return a = b, true;
  return false;
}

template<class T> bool maximize(T& a, T b){
  if(a < b) return a = b, true;
  return false;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int N = 1e5 + 5;

int n, lim, x[N]; ll c, s[N];

ll f(int l, int r){
  if(l == r) return 0;
  ll avg = x[l + r >> 1];
  int pos = l + r >> 1;

  int halfLeft = pos - l + 1;
  int halfRight = r - l + 1 - halfLeft;
  return (1LL * halfLeft * avg - (s[pos] - s[l - 1])) + ((s[r] - s[pos]) - 1LL * halfRight * avg);
}

int besthub(int R, int L, int X[0], ll B){
    n = R, lim = L; c = B;
    for(int i = 0; i < n; ++i){
      x[i + 1] = X[i];
      s[i + 1] = s[i] + X[i];
    }

    int ans = 0;
    for(int i = 1; i <= n; ++i){
      int l = 1, r = i, j = -1;
      while(l <= r){
        int mid = l + r >> 1;
        if(f(mid, i) <= c) j = mid, r = mid - 1;
        else l = mid + 1;
      }
      maximize(ans, i - j + 1);
    }
    return ans;
}

Compilation message (stderr)

ricehub.cpp: In function 'll f(int, int)':
ricehub.cpp:28:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |   ll avg = x[l + r >> 1];
      |              ~~^~~
ricehub.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int pos = l + r >> 1;
      |             ~~^~~
ricehub.cpp: In function 'int besthub(int, int, int*, ll)':
ricehub.cpp:47:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid = l + r >> 1;
      |                   ~~^~~

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 32 / 32