Submission #979916

#	Time	Username	Problem	Language	Result	Execution time	Memory
979916		SmuggingSpun	Rice Hub (IOI11_ricehub)	C++14	100 / 100	221 ms	8528 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
const int lim = 1e5 + 5;
int N = 1, ans = 0, cnt[lim], to_X[lim];
map<int, int>X_to;
ll sum[lim];
ll get_value(int p, int range){
	int P = lower_bound(to_X + 1, to_X + N + 1, to_X[p] - range) - to_X - 1;
	ll sum_left = 1LL * to_X[p] * (cnt[p] - cnt[P]) - sum[p] + sum[P];
	P = upper_bound(to_X + 1, to_X + N + 2, to_X[p] + range) - to_X - 1;
	return sum_left + sum[P] - sum[p] - 1LL * to_X[p] * (cnt[P] - cnt[p]);
}
int besthub(int n, int L, int X[], ll B){
	memset(cnt, 0, sizeof(cnt));
	memset(sum, 0, sizeof(sum));
	X_to[to_X[1] = X[0]] = 1;
	for(int i = 0; i < n; i++){
		if(i > 0 && X[i] != X[i - 1]){
			X_to[to_X[++N] = X[i]] = N;
		}
		cnt[N]++;
		sum[N] += X[i];
	}
	for(int i = 1; i <= N; i++){
		cnt[i] += cnt[i - 1];
		sum[i] += sum[i - 1];
	}
	to_X[N + 1] = INT_MAX;
	for(int i = 1; i <= N; i++){
		int low = 0, high = L, range;
		while(low <= high){
			int mid = (low + high) >> 1;
			if(get_value(i, mid) <= B){
				low = (range = mid) + 1;
			}
			else{
				high = mid - 1;
			}
		}
		ll remain = B - get_value(i, range);
		map<int, int>::iterator it = X_to.find(to_X[i] - range - 1);
		int add_cnt = 0; 
		if(it != X_to.end()){
			int can_add = min(ll(cnt[it->second] - cnt[it->second - 1]), remain / (range + 1));
			add_cnt += can_add;
			remain -= 1LL * can_add * (range + 1);
		}
		it = X_to.find(to_X[i] + range + 1);
		if(it != X_to.end()){
			add_cnt += min(ll(cnt[it->second] - cnt[it->second - 1]), remain / (range + 1));
		}
		maximize(ans, add_cnt + cnt[upper_bound(to_X + 1, to_X + N + 2, to_X[i] + range) - to_X - 1] - cnt[lower_bound(to_X + 1, to_X + N + 1, to_X[i] - range) - to_X - 1]);
	}
	return ans;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, ll)':
ricehub.cpp:26:14: warning: operation on 'N' may be undefined [-Wsequence-point]
   26 |    X_to[to_X[++N] = X[i]] = N;
      |              ^~~
ricehub.cpp:26:14: warning: operation on 'N' may be undefined [-Wsequence-point]
ricehub.cpp:48:50: warning: 'range' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |   map<int, int>::iterator it = X_to.find(to_X[i] - range - 1);
      |                                          ~~~~~~~~^~~~~~~

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