Submission #479196

#	Time	Username	Problem	Language	Result	Execution time	Memory
479196		khoabright	Packing Biscuits (IOI20_biscuits)	C++17	12 / 100	2 ms	332 KiB

biscuits

#include <bits/stdc++.h>
using namespace std;

//#define int long long 
#define ff first
#define ss second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define mp make_pair
#define vii vector<vector<int>>
#define ll long long 

ll count_tastiness(ll x, vector<ll> a) {
    function<void()> merge = [&]() {
        while(a.size()<61) a.push_back(0);
        int n = a.size();
        rep(i, 0, n - 2) {
            if (a[i] <= 2) continue;
            a[i + 1] += (a[i] - 1) / 2;   
            a[i] = 2 - (a[i] % 2);
        }
    };
    
    merge();
    ll ans = 1, cur = 0;

    // rep(i, 0, a.size() - 1) {
    //     cout << a[i] << ' ';
    // }
    //cout << '\n';
    rep1(k, 60, 0) {
        if (a[k] == 0) {
            ans *= (cur + 1);
            cur = 0;
            //the 0 seperate two segments because none of them is constrained to the other
        }  
        else {
            cur = cur * 2 + a[k];
            // x2 if for not use a[i] and use 1 * (2^i)
            // + a[i] means: if a[i] = 1, there is y = 2^i + 0*(2^(i+1)) + 0*...
            //if a[i] = 2, there is a possible value (the max one): 2*(2^i) + a[i+1]*(2^i+1) + ... (?)
            // explain (?): if we use 2*(2^i), then we cannot use (a[i+1]-x)*(2^i+1)  (for some x>0)
            //because we've already use (a[i+1]-x+1)*(2^i+1) 
            //i.e. 2*(2^i)+(a[i+1]-x)*(2^i+1) = (a[i+1]-x+1)*(2^i+1) 
            //=> we have to use a[i]*(2^i) for all i => max value. 
            //(This is the key reason why we iterate i from big to small)
        } 
    }
    ans *= (cur + 1);

    return ans;
}

// int main() {
//     long long x;
//     vector<long long> v(61);
//     cin >> x;
//     rep(i, 0, 4) {
//         cin >> v[i];
//     }
//     cout << count_tastiness(x, v);
// }

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