Submission #1212692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212692		hengliao	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	8 ms	952 KiB

biscuits

#pragma GCC optimize("O4,Ofast")
#include "biscuits.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define vll vector<ll>
#define pll pair<ll, ll>
#define pb push_back

typedef long long ll;
typedef __int128 i128;

namespace{
    ll k;
	const ll mxN=2e5+5;
	const ll inf=2e18;
    const ll LOG=63;
	ll a[LOG];
    ll b[LOG][2];
    ll mx[LOG];

    ll qry(ll bit, ll lef){
        if(bit==-1) return 1LL;
        lef=min(lef, mx[bit]);
        ll cur=(1LL<<(bit+1));
        if(lef>=cur/2){
            return qry(bit-1, lef-cur/2)+b[bit][0];
        }
        return qry(bit-1, lef);
    }
}

long long count_tastiness(long long x, vector<long long> A) {
	k=A.size();
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    for(ll i=0;i<k;i++){
        a[i]=A[i];
    }
    ll ans=1;
    ll lg=63-__builtin_clzll(inf/x);
    ll sum=0;

    for(ll bit=0;bit<=lg;bit++){
        // cout<<"bit: "<<bit<<'\n';
        sum+=(1LL<<bit)*a[bit];
        mx[bit]=sum/x;
        mx[bit]=min(mx[bit], (1LL<<(bit+1))-1);
        // cout<<"mx: "<<mx[bit]<<'\n';
        b[bit][0]=ans;
        if(mx[bit]&(1LL<<bit)){
            b[bit][1]=qry(bit-1, mx[bit]^(1LL<<bit));
        }
        ans+=b[bit][1];
        // cout<<"cur ans: "<<b[bit][0]<<' '<<b[bit][1]<<'\n';
    }

    // cout<<"_______\n";

    return ans;
}

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