Submission #335528

#	Time	Username	Problem	Language	Result	Execution time	Memory
335528		aanastasov	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	93 ms	1388 KiB

biscuits

#include "biscuits.h"

#include <cassert>

long long count_tastiness(long long x, std::vector<long long> a) {
	while (a.size() < 62) a.push_back(0);
	long long extra = 0;
	auto ways = std::vector<long long>{1};
	for (long long i = 0; i < a.size(); ++i) {
		if (a[i] + (extra >> i) >= x) {
			extra += (1LL << i) * a[i];
			extra -= (1LL << i) * x;
			assert(extra >= 0);
			ways.push_back(ways.back() * 2);
		} else {
			auto counts = std::vector<long long>(a.begin(), a.end());
			long long upper_bound = 0;
			for (long long j = i; j >= 0; --j) {
				long long available = 0;
				for (long long jj = 0; jj < j + 1; ++jj)
					available += counts[jj] * (1LL << jj);
				if ((available >> j) < x)
					continue;
				
				long long needed = x;
				for (long long jj = j; jj >= 0; --jj) {
					long long am = std::min(needed, counts[jj]);
					counts[jj] -= am;
					needed = (needed - am) * 2;
				}
				upper_bound |= 1LL << j;
			}
			long long res = 0;
			upper_bound++;
			for (long long j = 0; j < i + 1; ++j)
				if ((upper_bound & (1LL << j)) > 0)
					res += ways[j];
			ways.push_back(res);
			extra = 0;
		}
	}
	return ways.back();
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:9:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for (long long i = 0; i < a.size(); ++i) {
      |                        ~~^~~~~~~~~~

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