Submission #529020

#	Time	Username	Problem	Language	Result	Execution time	Memory
529020		SHZhang	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	47 ms	26792 KiB

biscuits

#include "biscuits.h"
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

#define ll long long

using namespace std;

struct Node {
	Node* left;
	Node* right;
	ll count;
	Node() : left(NULL), right(NULL), count(0) {}
};

Node* clone(Node* node, ll dep, ll maxv)
{
	if (!node) return NULL;
	if (maxv >= (1LL << dep) - 1) {return node;}
	Node* ans = new Node;
	if (maxv >= (1LL << (dep - 1))) {
		ans->left = node->left;
		ans->right = clone(node->right, dep - 1, maxv - (1LL << (dep - 1)));
		ans->count = (ans->left ? ans->left->count : 0) +
			(ans->right ? ans->right->count : 0);
	} else {
		ans->left = clone(node->left, dep - 1, maxv);
		ans->right = NULL;
		ans->count = (ans->left ? ans->left->count : 0);
	}
	return ans;
}

ll count_tastiness(ll x, vector<ll> a) {
	while (a.size() < 60) a.push_back(0LL);
	Node* root = new Node; root->count = 1;
	Node* curnode = root;
	for (int i = 1; i <= 62; i++) {
		curnode->left = new Node;
		curnode = curnode->left;
		curnode->count = 1;
	}
	ll cursum = 0;
	for (ll i = 0; i < 60; i++) {
		ll prevneed = max(x - a[i], 0LL);
		//printf("%lld %lld\n", i, prevneed);
		if (prevneed <= (cursum >> i) && (cursum - (prevneed << i)) >= 0) {
			ll maxlast = (cursum - (prevneed << i)) / x;
			maxlast = min(maxlast, (1LL << i) - 1);
			//printf("%lld %lld ", i, maxlast);
			Node* dupnode = root;
			for (int j = 1; j <= 61 - i; j++) dupnode = dupnode->left;
			Node* resnode = clone(dupnode->left, i, maxlast);
			//printf("%lld %lld\n", dupnode->left->count, resnode->count);
			dupnode->right = resnode;
			dupnode = root; root->count += resnode->count;
			for (int j = 1; j <= 61 - i; j++) {
				dupnode = dupnode->left;
				dupnode->count += resnode->count;
			}
		}
		cursum += (a[i] << i);
	}
	return root->count;
}

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