oj.uz

Submission #43666

# Submission time Handle Problem Language Result Execution time Memory
43666 2018-03-19T09:17:46 Z baactree Rice Hub (IOI11_ricehub) C++14
17 / 100
 72 ms 3444 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 2 ms 552 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 560 KB Output is correct
2 Correct 1 ms 560 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 1 ms 580 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 632 KB Output is correct
7 Correct 1 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 1 ms 632 KB Output is correct
11 Incorrect 1 ms 632 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Incorrect 2 ms 632 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1272 KB Output is correct
2 Correct 39 ms 1272 KB Output is correct
3 Correct 59 ms 3440 KB Output is correct
4 Correct 72 ms 3444 KB Output is correct
5 Incorrect 20 ms 3444 KB Output isn't correct
6 Halted 0 ms 0 KB -