Submission #43666

#	Time	Username	Problem	Language	Result	Execution time	Memory
43666		baactree	Rice Hub (IOI11_ricehub)	C++14	17 / 100	72 ms	3444 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll b;
int r, l, x[100005];
ll cnt[100005], sum[100005];
vector<int> xidx;
bool possi(int k) {
	int lcnt = k / 2;
	int rcnt = k - lcnt;
	ll ret = 0x3f3f3f3f3f3f3f3f;
	int cs = 0;
	for (int i = 1; i < xidx.size(); i++) {
		if (cnt[i - 1] < lcnt || cnt[xidx.size() - 1] - cnt[i - 1] < rcnt)continue;
		int ridx = lower_bound(cnt, cnt + xidx.size(), cnt[i-1] + rcnt) - cnt;
		int lidx = upper_bound(cnt, cnt + xidx.size(), cnt[i-1] - lcnt) - cnt;
		lidx = max(1, lidx);
		ridx = min((int)xidx.size() - 1, ridx);
		ll now = (sum[ridx - 1] - sum[i - 1]) - (cnt[ridx - 1] - cnt[i - 1])*xidx[i];
		ll r = rcnt - (cnt[ridx - 1] - cnt[i - 1]);
		now += r * (xidx[ridx] - xidx[i]);
		now += (cnt[i - 1] - cnt[lidx-1])*xidx[i] - (sum[i - 1] - sum[lidx-1]);
		r = lcnt - (cnt[i - 1] - cnt[lidx-1]);
		now += r * (xidx[i] - xidx[lidx-1]);
		ret = min(ret, now);
	}
	return ret <= b;
}
int besthub(int R, int L, int X[], long long B)
{
	r = R; l = L; b = B;
	for (int i = 0; i < r; i++) {
		x[i] = X[i];
		xidx.push_back(x[i]);
	}
	xidx.push_back(0);
	sort(xidx.begin(), xidx.end());
	xidx.erase(unique(xidx.begin(), xidx.end()), xidx.end());
	for (int i = 0; i < r; i++) {
		cnt[lower_bound(xidx.begin(), xidx.end(), x[i]) - xidx.begin()]++;
		sum[lower_bound(xidx.begin(), xidx.end(), x[i]) - xidx.begin()] += x[i];
	}
	for (int i = 1; i < xidx.size(); i++) {
		cnt[i] += cnt[i - 1];
		sum[i] += sum[i - 1];
	}
	int le, ri, mid, ans;
	ans = 0;
	le = 1;
	ri = r;
	while (le <= ri) {
		mid = (le + ri) / 2;
		if (possi(mid)) {
			ans = mid;
			le = mid + 1;
		}
		else
			ri = mid - 1;
	}
	return ans;
}

Compilation message (stderr)

ricehub.cpp: In function 'bool possi(int)':
ricehub.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < xidx.size(); i++) {
                    ^
ricehub.cpp:13:6: warning: unused variable 'cs' [-Wunused-variable]
  int cs = 0;
      ^
ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < xidx.size(); i++) {
                    ^

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