Submission #569340

#	Time	Username	Problem	Language	Result	Execution time	Memory
569340		Stickfish	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	1086 ms	14632 KiB

biscuits

#include "biscuits.h"
#include <iostream>
using namespace std;
using ll = long long;

const ll INF = 1e18 + 177013;

vector<pair<ll, ll>> unite_same(vector<pair<ll, ll>>& vcnts) {
    vector<pair<ll, ll>> ans;
    for (auto p : vcnts) {
        if (ans.empty() || ans.back().first < p.first)
            ans.push_back(p);
        else
            ans.back().second += p.second;
    }
    return ans;
}

vector<pair<ll, ll>> merge(vector<pair<ll, ll>>& a, vector<pair<ll, ll>>& b) {
    int n = a.size();
    int m = b.size();
    int j = 0;
    vector<pair<ll, ll>> ans;
    for (int i = 0; i < n; ++i) {
        while (j < m && b[j].first <= a[i].first) {
            ans.push_back(b[j]);
            ++j;
        }
        if (ans.size() && ans.back().first == a[i].first)
            ans.back().second += a[i].second;
        else
            ans.push_back(a[i]);
    }
    while (j < m) {
        ans.push_back(b[j]);
        ++j;
    }
    return ans;
}

ll count_tastiness(ll x, vector<ll> a) {
    int k = a.size();
    vector<pair<ll, ll>> vcnts;
    vcnts.push_back({0, 1});
    for (int i = 0; x * (1ll << i) < INF; ++i) {
        for (auto& [t, cnt] : vcnts) {
            t >>= 1;
            if (i < k)
                t += a[i];
        }
        vcnts = unite_same(vcnts);
        if (vcnts.back().first < x)
            continue;
        vector<pair<ll, ll>> addv;
        for (auto p : vcnts) {
            if (p.first >= x)
                addv.push_back({p.first - x, p.second});
        }
        vcnts = merge(vcnts, addv);
        if (vcnts.size() > 10000000)
            return -1;
    }
    ll ans = 0;
    for (auto [t, cnt] : vcnts)
        ans += cnt;
    return ans;
}

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