Submission #934065

#	Time	Username	Problem	Language	Result	Execution time	Memory
934065		EJIC_B_KEDAX	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	12 ms	1384 KiB

biscuits

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

mt19937 mt(time(nullptr));

vector<ll> tmp, origin, dp;

ll calc(ll x, int pos) {
    ll sum = (1ll << pos) * tmp[pos];
    int ptr = pos;
    while (ptr > 0 && sum < (__int128)1 * (1ll << pos) * x) {
        sum += (1ll << ptr) * tmp[--ptr];
    }
    if (sum < (__int128)1 * (1ll << pos) * x) {
        // cout << "! " << pos << '\n';
        return (pos ? dp[pos - 1] : 1);
    }
    if (ptr == pos) {
        // cout << "!! " << pos << '\n';
        if (ptr == 0) {
            return 2;
        } else {
            return 2 * dp[pos - 1];
        }
    }
    tmp[ptr] = (sum - (__int128)1 * (1ll << pos) * x) / (1ll << ptr);
    ll res = calc(x, ptr);
    // cout << pos << ' ' << ptr << ' ' << res << '\n';
    tmp[ptr] = origin[ptr];
    return res + dp[pos - 1];
}

ll count_tastiness(ll x, vector<ll> a) {
    while (a.size() < 60) {
        a.push_back(0);
    }
    int n = 60;
    for (int i = 0; i < n; i++) {
        if (a[i] > x + 1) {
            a[i + 1] += (a[i] - x) / 2;
            a[i] -= ((a[i] - x) / 2) * 2;
        }
    }
    origin = a;
    tmp.resize(n);
    tmp = a;
    dp.resize(n, 0);
    for (int i = 0; i < n; i++) {
        dp[i] = calc(x, i);
        // cout << dp[i] << '\n';
    }
    // cout << '\n';
    return dp[n - 1];
}

Compilation message (stderr)

biscuits.cpp: In function 'll calc(ll, int)':
biscuits.cpp:15:35: warning: operation on 'ptr' may be undefined [-Wsequence-point]
   15 |         sum += (1ll << ptr) * tmp[--ptr];
      |                                   ^~~~~

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