Submission #335533

#	Time	Username	Problem	Language	Result	Execution time	Memory
335533		aanastasov	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	21 ms	876 KiB

biscuits

#include "biscuits.h"

#include <cassert>

typedef long long int64_t;

int64_t count_tastiness(int64_t numGroups, std::vector<int64_t> initialCount) {
    while (initialCount.size() < 62) initialCount.push_back(0);
    int64_t spareCount = 0;
    auto numWays = std::vector<int64_t>{1};
    for (int64_t i = 0; i < initialCount.size(); ++i) {
        if (initialCount[i] + spareCount >= numGroups) {
            spareCount = spareCount + initialCount[i] - numGroups;
            assert(spareCount >= 0);
            numWays.push_back(numWays.back() * 2);
        } else {
            auto counts = std::vector<int64_t>(initialCount.begin(), initialCount.end());
            int64_t availableQty = 0;
            for (int64_t j = 0; j <= i; ++j) availableQty += counts[j] << j;
            int64_t totalBorrowedQty = 0;
            int64_t maxPossible = 0;
            for (int64_t j = i; j >= 0; --j) {
                bool okay = ((availableQty - totalBorrowedQty) >> j) >= numGroups;
                if (okay) {
                    totalBorrowedQty += numGroups << j;
                    totalBorrowedQty = std::max(0LL, totalBorrowedQty - (counts[j] << j));
                    maxPossible |= 1LL << j;
                }
                availableQty -= counts[j] << j;
            }
            int64_t curWays = 0;
            for (int64_t j = 0; j < i + 1; ++j) {
                if (((maxPossible + 1) & (1LL << j)) > 0) curWays += numWays[j];
            }
            numWays.push_back(curWays);
            spareCount = 0;
        }
        spareCount >>= 1LL;
    }
    return numWays.back();
}

Compilation message (stderr)

biscuits.cpp: In function 'int64_t count_tastiness(int64_t, std::vector<long long int>)':
biscuits.cpp:11:27: 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 < initialCount.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~

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