Submission #1069919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069919		jerzyk	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	21 ms	7548 KiB

biscuits

#include <bits/stdc++.h>
#include "biscuits.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int H = 60;
const ll N = (1LL<<(ll)H);
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int NN = 1000 * 1000 + 7;
ll drz[NN], il[NN];
int l[NN], r[NN]; int cnt;
ll answer = 0LL;

void Init()
{
    for(int i = 1; i <= 4000; ++i)
    {
        drz[i] = 0LL; l[i] = 0; r[i] = 0;
    }
    for(int i = 1; i <= H; ++i)
        {l[i] = i + 1; drz[i] = 1LL;}
    drz[H + 1] = 1LL;
    cnt = H + 1;
}

void Copy(int v1, int v2, ll a, ll b, ll lim)
{
    if((a + b) / 2LL <= lim)
        l[v2] = l[v1];

    if((a + b) / 2LL > lim)
    {
        if(l[v1] != 0)
        {
            ++cnt; l[v2] = cnt;
            Copy(l[v1], l[v2], a, (a + b) / 2LL, lim);
        }
    }
    if((a + b) / 2LL < lim)
    {
        if(r[v1] != 0)
        {
            ++cnt; r[v2] = cnt;
            Copy(r[v1], r[v2], (a + b) / 2LL + 1LL, b, lim);
        }
    }
    //cerr << v2 << " Copy " << l[v2] << " " << r[v2] << "\n";
    drz[v2] = drz[l[v2]] + drz[r[v2]];
}

void Upd(ll b, ll lim)
{
    int v1;
    ll ran = (N - 1LL) / 2LL;
    v1 = 1;
    while(ran + 1LL > b)
    {
        ran /= 2LL; v1 = l[v1];
    }
    //cerr << b << " " << "Upd: " << v1 << " " << ran << " " << lim << "\n";
    if(lim >= b - 1LL)
    {
        r[v1] = l[v1];
    }else
    {
        ++cnt;
        r[v1] = cnt;
        //cerr << "cp " << l[v1] << " " << r[v1] << "\n";
        Copy(l[v1], r[v1], 0, ran, lim);
    }
    while(v1 > 0)
    {
        drz[v1] = drz[l[v1]] + drz[r[v1]];
        --v1;
    }
}

long long count_tastiness(long long x, vector<long long> _a)
{
    Init();
    int n = _a.size() - 1;
    for(int i = 0; i <= n; ++i)
        il[i] = _a[i];
    if(il[0] >= x)
        Upd(1LL, 0LL);
    //cerr << "DP: \n";
    for(int i = 1; i <= 60; ++i)
    {
        if(x * (1LL<<(ll)i) > (ll)I) break;
        il[i] *= (1LL<<(ll)i);
        ll ned = max(0LL, (x * (1LL<<(ll)i) - il[i]));
        ll lim = (il[i - 1] - ned) / x;
        if(il[i - 1] - ned < 0LL)
            lim = -1LL;
        lim = min(lim, (1LL<<(ll)(i)) - 1LL);
        //cerr << i << " " << "bis: " << ned << " " << lim << "\n";
        if(lim >= 0LL)
            Upd((1LL<<(ll)i), lim);
        il[i] += il[i - 1];
        //cerr << drz[1] << "\n";
    }
    for(int i = 0; i <= 100; ++i)
        il[i] = 0LL;
    return drz[1];
}

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