Submission #1186765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186765		owoovo	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	25 ms	956 KiB

biscuits

#include "biscuits.h"
#include<bits/stdc++.h>
#define ll long long 
#define F first 
#define S second 
using namespace std;
ll pre[62],xd[62],al[62];
int k;
map<ll,ll> mp[62];// bitmask sz
ll count_tastiness(ll x, vector<ll> b) {
	ll zero=1;
	ll a[62]={};
	for(int i=0;i<b.size();i++)a[i]=b[i];
	k=61;
	for(int i=0;i<k;i++){
		mp[i].clear();
	}
	pre[0]=a[0];
	xd[0]=pre[0]/x;
	xd[0]=min(xd[0],1ll);
	if(xd[0]>=1)zero++;
	for(int i=1;i<k;i++){
		pre[i]=pre[i-1]+a[i]*(1ll<<i);
		xd[i]=pre[i]/x;
		xd[i]=min(xd[i],(1ll<<(i+1))-1);
		//cout<<xd[i]<<" "<<i<<" ?\n";
		if(xd[i]>=(1ll<<(i))){
			ll real=xd[i];
			//cout<<real<<" "<<i<<" xd\n";
			real-=(1ll<<i);
			if(real==0){
				zero+=1;
			}else{
				ll clz=__countl_zero(real);
				ll hb=62-clz;
				mp[hb][real]+=1;
			}
		}
	}
	for(int i=k-1;i>=0;i--){
		for(auto tar:mp[i]){
			ll real=min(tar.F,xd[i]),sz=tar.S;
			//cout<<real<<" "<<sz<<"\n";
			// dont take i
			// if(i==0){
			// 	zero+=sz;
			// }else{
			// 	mp[i-1][(1LL<<i)-1]+=sz;
			// }
			// take i
			if(real>=(1ll<<i)){ 
				real-=(1ll<<i);
				if(i==0)zero+=sz;
				else{
					mp[i-1][(1ll<<i)-1]+=sz;
				}
				if(real==0){
					zero+=sz;
				}else{
					ll clz=__countl_zero(real);
					ll hb=62-clz;
					mp[hb][real]+=sz;
				}
			}else{
				if(real==0){
					zero+=sz;
				}else{
					ll clz=__countl_zero(real);
					ll hb=62-clz;
					mp[hb][real]+=sz;
				}
			}
		}
		// do al

	}

	return zero;
}

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