제출 #1214874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214874		Math4Life2020	비스킷 담기 (IOI20_biscuits)	C++20	100 / 100	28 ms	1092 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)) {
        if (mem[v][1]!=-1) {
            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]});
        } else {
            mem.push_back({mem[v][0],-1,ht,mem[mem[v][0]][3]});
        }
        return (mem.size()-1);
    } else {
        ll vnew = split(mem[v][0],y);
        mem.push_back({vnew,-1,ht,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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 21 / 21
• Subtask 4: 35 / 35
• Subtask 5: 23 / 23