Submission #385226

#	Time	Username	Problem	Language	Result	Execution time	Memory
385226		rqi	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	22 ms	1388 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;

#define sz(x) (int)(x).size()
#define pb push_back

int k;
vl a;
ll x;

ll tpow[64];

bool possible(ll y){
	vl A = a;
	
	for(int i = 0; i <= 59; i++){
		if((y>>i)&1){
			A[i]-=x;
		}
		
		if(A[i] < 0) return 0;
		if(i+1 < 60){
			A[i+1]+=A[i]/2;
		}
	}
	//cout << y << "\n";
	return 1;
}

ll solveCase1(){
	while(sz(a) < 60){
		a.pb(0);
	}
	int ans = 0;
	for(int y = 0; y <= 100000; y++){
		if(possible(y)){
			ans++;
		}
	}
	return ans;
}

ll restr[62];
ll dp[62];

ll getDP(ll v, int bitnum){
	// if(v != 0 && 63- __builtin_clzll(v) > bitnum){
	// 	cout << v << " " << bitnum << "\n";
	// }
	assert(v == 0 || 63- __builtin_clzll(v)  <= bitnum);
	assert(v >= 0);
	if(v == 0){
		return 1;
	}
	if(bitnum == 0){
		if(v == 0){
			return 1;
		}
		else if(v == 1){
			return dp[bitnum];
		}
		assert(false);
	}

	if(v < tpow[bitnum]){
		return getDP(v, bitnum-1);
	}

	if(restr[bitnum] < tpow[bitnum]){
		return getDP(restr[bitnum], bitnum-1);
	}

	return dp[bitnum-1]+getDP(min(v-tpow[bitnum], restr[bitnum]-tpow[bitnum]), bitnum-1);
}

ll count_tastiness(ll _x, vl _a) {
	x = _x;
	a = _a;
	while(sz(a) < 62){
		a.pb(0);
	}

	k = sz(a);

	tpow[0] = 1;
	for(int i = 1; i < 64; i++){
		tpow[i] = tpow[i-1]*2;
	}

	// bool CASE1 = 1;

	// if(CASE1){
	// 	return solveCase1();
	// }

	restr[0] = a[0];
	for(int i = 1; i <= 61; i++){
		restr[i] = restr[i-1]+tpow[i]*a[i];
	}

	for(int i = 0; i <= 61; i++){
		restr[i]/=x;
	}

	if(restr[0] >= 1){
		dp[0] = 2;
	}
	else{
		dp[0] = 1;
	}

	for(int i = 1; i <= 61; i++){
		dp[i] = getDP(tpow[i+1]-1, i);
	}

	//assert(solveCase1() == dp[59]);
	assert(dp[59] == dp[60] && dp[60] == dp[61]);
	return dp[59];
}

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