Submission #335538

#	Time	Username	Problem	Language	Result	Execution time	Memory
335538		aanastasov	비스킷 담기 (IOI20_biscuits)	C++17	Compilation error	0 ms	0 KiB

biscuits

#include "biscuits.h"
 
#include <cassert>
#include <iostream>
 
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 maxPossible = 0;
            int64_t totalAvailableQty = 0;
            for (int64_t j = 0; j <= i; ++j) totalAvailableQty += counts[j] << j;
            int64_t totalBorrowedQty = 0;
            for (int64_t j = i; j >= 0; --j) {
                int64_t availableQty = 0;
                for (int64_t jj = 0; jj < j + 1; ++jj)
                    availableQty += counts[jj] << jj;
                assert(totalAvailableQty >= totalBorrowedQty);
                assert((totalBorrowedQty % (1LL << j)) == 0);
                int64_t curCount = initialCount[j];
                if ((curCount << j) <= totalBorrowedQty) {
                    totalBorrowedQty -= curCount << j;
                    totalAvailableQty -= curCount << j;
                    curCount = 0;
                } else {
                    curCount -= totalBorrowedQty >> j;
                    totalAvailableQty -= totalBorrowedQty;
                    totalBorrowedQty = 0;
                }
                assert(curCount >= 0 && curCount <= initialCount[j]);
                //std::cout << availableQty << " " << totalAvailableQty << " " << totalBorrowedQty << std::endl;
                assert(availableQty == (totalAvailableQty - totalBorrowedQty));
                if ((availableQty >> j) < numGroups) {
                    totalAvailableQty -= curCount << j;
                    continue;
                }
                totalBorrowedQty += numGroups << j;
                if ((curCount << j) >= totalBorrowedQty)
                    totalBorrowedQty = 0;
                else
                    totalBorrowedQty -= curCount << j;
                totalAvailableQty -= curCount << j;
                
                int64_t borrowedQty = numGroups;
                for (int64_t jj = j; jj >= 0; --jj) {
                    int64_t takeCount = std::min(borrowedQty, counts[jj]);
                    counts[jj] -= takeCount;
                    borrowedQty = (borrowedQty - takeCount) << 1LL;
                }
                assert(borrowedQty == 0);
                maxPossible |= 1LL << j;
            }
            assert(totalBorrowedQty == 0);
            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:6:19: error: conflicting declaration 'typedef long long int int64_t'
    6 | typedef long long int64_t;
      |                   ^~~~~~~
In file included from /usr/include/stdint.h:34,
                 from /usr/lib/gcc/x86_64-linux-gnu/9/include/stdint.h:9,
                 from /usr/include/c++/9/cstdint:41,
                 from /usr/include/c++/9/bits/char_traits.h:621,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/ostream:38,
                 from /usr/include/c++/9/iostream:39,
                 from biscuits.cpp:4:
/usr/include/x86_64-linux-gnu/bits/stdint-intn.h:27:19: note: previous declaration as 'typedef __int64_t int64_t'
   27 | typedef __int64_t int64_t;
      |                   ^~~~~~~
biscuits.cpp: In function 'int64_t count_tastiness(int64_t, std::vector<long int>)':
biscuits.cpp:12:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int64_t i = 0; i < initialCount.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~