Submission #648773

#	Time	Username	Problem	Language	Result	Execution time	Memory
648773		ymm	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	561 ms	1356 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int K = 130;
vector<pll> dif[K];
ll cnt[K];
ll x;

ll f(int i, ll x)
{
	auto it = upper_bound(dif[i].begin(), dif[i].end(), pll{x, 2e18});
	--it;
	return it->second;
}

ll f_next(int i, ll x)
{
	ll val = 0;
	val += f(i+1, cnt[i+1] + x/2);
	if (x>=::x) {
		ll mv = x-::x;
		val += f(i+1, cnt[i+1] + mv/2);
	}
	return val;
}

ll get_next(int i, ll pre, ll pre_val)
{
	ll l = pre+1;
	ll r = 2*x+2;
	while (l<r) {
		ll mid = (l+r)/2;
		ll val = f_next(i, mid);
		if (val > pre_val)
			r = mid;
		else
			l = mid+1;
	}
	return l;
}

long long count_tastiness(long long x, std::vector<long long> a)
{
	::x = x;
	Loop (i,0,a.size())
		cnt[i] = a[i];
	Loop (i,a.size(),K)
		cnt[i] = 0;
	Loop (i,0,K-1) {
		ll mv = cnt[i]-x;
		if (mv <= 1)
			continue;
		mv &= -2;
		cnt[i] -= mv;
		cnt[i+1] += mv/2;
	}
	dif[K-1] = {{0, 1}, {x, 2}, {2*x, 3}};
	LoopR (i,0,K-1) {
		ll pre = 0, pre_val = f(i+1, cnt[i+1]);
		dif[i] = {{pre, pre_val}};
		for (;;) {
			ll nxt = get_next(i, pre, pre_val);
			if (nxt == 2*x+2)
				break;
			pre = nxt;
			pre_val = f_next(i, nxt);
			//printf("%d %ld %ld\n", i, pre, pre_val);
			dif[i].push_back({pre, pre_val});
		}
	}
	return f(0, cnt[0]);
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 21 / 21
• Subtask 4: 35 / 35
• Subtask 5: 23 / 23