Submission #335530

#	Time	Username	Problem	Language	Result	Execution time	Memory
335530		aanastasov	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	97 ms	1028 KiB

biscuits

#include "biscuits.h"

#include <cassert>

typedef long long int64_t;

int64_t count_tastiness(int64_t x, std::vector<int64_t> a) {
	while (a.size() < 62) a.push_back(0);
	int64_t extra = 0;
	auto ways = std::vector<int64_t>{1};
	for (int64_t 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<int64_t>(a.begin(), a.end());
			int64_t upper_bound = 0;
			for (int64_t j = i; j >= 0; --j) {
				int64_t available = 0;
				for (int64_t jj = 0; jj < j + 1; ++jj)
					available += counts[jj] * (1LL << jj);
				if ((available >> j) < x)
					continue;
				
				int64_t needed = x;
				for (int64_t jj = j; jj >= 0; --jj) {
					int64_t am = std::min(needed, counts[jj]);
					counts[jj] -= am;
					needed = (needed - am) * 2;
				}
				upper_bound |= 1LL << j;
			}
			int64_t res = 0;
			upper_bound++;
			for (int64_t 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 'int64_t count_tastiness(int64_t, std::vector<long long int>)':
biscuits.cpp:11:24: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for (int64_t 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