Submission #1214870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214870		Math4Life2020	Packing Biscuits (IOI20_biscuits)	C++20	0 / 100	3 ms	584 KiB

biscuits

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
using ui = __int128_t; using ui4 = array<ui,4>;

#include "biscuits.h"

vector<ui4> mem;
//left, right, height, # contained
ll root;

ll split(ll v, ll y) {
    //handle height = -1
    ll ht = mem[v][2];
    if (ht==-1) {
        mem.push_back({-1,-1,-1,1});
        return (mem.size()-1);
    }
    if (y>=(((ui)1)<<ht)) {
        ll vnew = split(mem[v][1],y-(((ui)1)<<ht));
        mem.push_back({mem[v][0],vnew,ht,mem[mem[v][0]][3]+mem[vnew][3]});
        return (mem.size()-1);
    } else {
        ll vnew = split(mem[v][0],y);
        mem.push_back({vnew,mem[v][1],ht,mem[mem[1][0]][3]+mem[vnew][3]});
        return (mem.size()-1);
    }
}

ll count_tastiness(ll x, vector<ll> a0) {
    ll k = a0.size();
    mem.clear();
    mem.push_back({-1,-1,-1,1});
    root = 0;
    while (a0.size()<=60) {
        a0.push_back(0);
    }
    k = a0.size();
    ui y0 = 0; //current sum
    for (ll i=0;i<k;i++) {
        y0 += ((ui)a0[i])<<i;
        ui z0 = y0/x;
        z0 = min(z0,(((ui)1)<<(i+1))-1);
        if (z0>=(((ui)1)<<i)) {
            ll vnew = split(root,z0-(((ui)1)<<(i)));
            mem.push_back({root,vnew,i,mem[root][3]+mem[vnew][3]});
            root = mem.size()-1;
        }
    }
    return mem[root][3];
}

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