Submission #781490

#	Time	Username	Problem	Language	Result	Execution time	Memory
781490		asdfgrace	Rice Hub (IOI11_ricehub)	C++17	100 / 100	225 ms	5700 KiB

ricehub

#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
#define PAR2D(x) DEBUG(PRINT(#x << ":\n"); for (auto arr : x) {PAR(arr);} PRINT('\n'));
using i64 = long long;
const int INF = 1000000007; //998244353;

int besthub(int R, int L, int X[], i64 B) {
  vector<pair<i64, i64>> at;
  for (int i = 0; i < R; ++i) {
    if (i == 0 || X[i] != X[i - 1]) at.push_back({X[i], 1LL});
    else ++at.back().second;
  }
  int n = (int)at.size();
  // for each city, find maximum number WITHIN BUDGET
  // this can be done greedily
  // if we add in the order of distance from current city
  // we can binary search (yes!!!) for the size of the outer bound
  // nlog^2n probably passes as well
  vector<pair<i64, i64>> pref(n);
  vector<i64> cd(n);
  pref[0] = at[0];
  cd[0] = at[0].first * at[0].second;
  for (int i = 1; i < n; ++i) {
    pref[i].first = pref[i - 1].first + at[i].first;
    pref[i].second = pref[i - 1].second + at[i].second;
    cd[i] = cd[i - 1] + at[i].first * at[i].second;
  }
  PAR2(at); PAR2(pref);
  auto cost = [&] (i64 m, int i) -> i64 {
    int lb = lower_bound(at.begin(), at.end(),
      make_pair(at[i].first - m, 0LL)) - at.begin();
    int rb = upper_bound(at.begin(), at.end(),
      make_pair(at[i].first + m, 0LL)) - at.begin() - 1;
    i64 ldist = cd[i] - cd[lb] + at[lb].first * at[lb].second;
    i64 lcnt = pref[i].second - pref[lb].second + at[lb].second;
    i64 rdist = cd[rb] - cd[i] + at[i].first * at[i].second;
    i64 rcnt = pref[rb].second - pref[i].second + at[i].second;
    //PV(lcnt); PV(ldist); PV(rcnt); PV(rdist);
    return lcnt * at[i].first - ldist + rdist - rcnt * at[i].first;
  };
  auto abval = [&] (i64 x) -> i64 {
    return max(x, -x);
  };
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    i64 l = 0, r = L;
    // make sure it COMPLETELY works
    // then we can add on the edges if needed
    while (r > l + 1) {
      i64 m = (l + r) / 2;
      //PV(m);
      //PV(cost(m, i));
      if (cost(m, i) <= B) {
        l = m;
      } else {
        r = m - 1;
      }
    }
    i64 res = (cost(r, i) <= B ? r : l), c = cost(res, i);
    PV(res); PV(c);
    int lb = lower_bound(at.begin(), at.end(),
      make_pair(at[i].first - res, 0LL)) - at.begin();
    int rb = upper_bound(at.begin(), at.end(),
      make_pair(at[i].first + res, 0LL)) - at.begin() - 1;
    int cnt = pref[rb].second - pref[lb].second + at[lb].second;
    PV(cnt);
    if (c < B) {
      vector<pair<i64, i64>> extras;
      PV(lb); PV(rb);
      if (lb > 0) extras.push_back(at[lb - 1]);
      if (rb < n - 1) extras.push_back(at[rb + 1]);
      sort(extras.begin(), extras.end(), [&](pair<i64, i64> a, pair<i64, i64> b) {
        return a.first - at[i].first < b.first - at[i].first;
        });
      for (int j = 0; j < (int) extras.size(); ++j) {
        i64 rem = B - c, used = min(rem / abval(extras[j].first - at[i].first), extras[j].second);
        cnt += used;
        c += abval(extras[j].first - at[i].first) * used;
      }
      PAR2(extras); PV(cnt); PV(c);
    }
    ans = max(ans, cnt);
  }
  return ans;
}

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