Submission #304376

#	Time	Username	Problem	Language	Result	Execution time	Memory
304376		kevinsogo	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	285 ms	1016 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template<class T>
void sort_uniq(vector<T>& v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

ll count_tastiness(ll x, vector<ll> a) {
    for (int i = 0; i < a.size(); i++) {
        if (a[i] > x) {
            ll e = a[i] - x >> 1 << 1;
            a[i] -= e;
            if (i + 1 == a.size()) a.push_back(0LL);
            a[i + 1] += e >> 1;
        }
        assert(a[i] <= x + 1);
    }

    ll up = 2*x + 1;
    for (ll r = up; r > 0; r >>= 1) a.push_back(0LL);
    a.push_back(0LL);

    ll val = 0;
    vector<ll> ans(1, 1LL), bds(1);
    auto g = [&](ll v) {
        return v >= 0 ? ans[distance(bds.begin(), upper_bound(bds.begin(), bds.end(), (v >> 1) + val)) - 1] : 0;
    };
    for (int i = a.size(); i--;) {
        vector<ll> bbds(1);
        for (ll b : bds) if (b != 1 || x == 1) bbds.push_back(b - val << 1);
        for (int i = bbds.size(); i--;) bbds.push_back(bbds[i] + x);
        bbds.push_back(1LL);
        sort_uniq(bbds);
        while (bbds.back() > up) bbds.pop_back();
        auto e = bbds.begin();
        while (*e < 0) e++;
        bbds.erase(bbds.begin(), e);
        vector<ll> bans;
        for (ll v : bbds) bans.push_back(g(v) + g(v - x));
        bds = bbds;
        ans = bans;
        val = a[i];
    }

    return g(0);
}

Compilation message (stderr)

biscuits.cpp: In function 'll count_tastiness(ll, std::vector<long long int>)':
biscuits.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~
biscuits.cpp:15:25: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   15 |             ll e = a[i] - x >> 1 << 1;
biscuits.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |             if (i + 1 == a.size()) a.push_back(0LL);
      |                 ~~~~~~^~~~~~~~~~~
biscuits.cpp:34:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   34 |         for (ll b : bds) if (b != 1 || x == 1) bbds.push_back(b - val << 1);
      |                                                               ~~^~~~~

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