Submission #1227927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227927		omsincoconut	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	1093 ms	14732 KiB

biscuits

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

ll count_tastiness(ll x, vector<ll> a) {
    a.resize(128);

    vector<pll> c = {{0, 1}};

    for (ll i = 0; i < 120; i++) {
        vector<pll> nc, ncd;
        for (pair<ll, ll> uv : c) {
            ll u, v;
            tie(u, v) = uv;
            u = (u>>1)+a[i];
            nc.emplace_back(u, v);
            if (u >= x) ncd.emplace_back(u-x, v);
        }

        int ptrl = 0, ptrr = 0;
        vector<pll> nnc;
        while (ptrl < nc.size() && ptrr < ncd.size()) {
            ll u, v;
            if (nc[ptrl].first < ncd[ptrr].first) tie(u, v) = nc[ptrl++];
            else tie(u, v) = ncd[ptrr++];

            if (nnc.empty() || nnc.back().first != u) nnc.emplace_back(u, v);
            else nnc.back().second += v;
        }

        while (ptrl < nc.size()) {
            ll u, v;
            tie(u, v) = nc[ptrl++];
            if (nnc.empty() || nnc.back().first != u) nnc.emplace_back(u, v);
            else nnc.back().second += v;
        }

        while (ptrr < ncd.size()) {
            ll u, v;
            tie(u, v) = nc[ptrr++];
            if (nnc.empty() || nnc.back().first != u) nnc.emplace_back(u, v);
            else nnc.back().second += v;
        }

        c = nnc;
    }

    ll ans = 0;
    for (auto [u, v] : c) ans += v;
    return ans;
}

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