Submission #1082004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082004		vjudge1	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	15 ms	1444 KiB

biscuits

#include "biscuits.h"

#include <iostream>

struct Node {
	Node *left, *right;
	long long sum;
};

int c = 0;
Node buffer[50000];

Node* build(Node* node, __int128 l, __int128 r, __int128 lim) {
	if(r <= lim || node->sum == 0) {
		return node;
	}
	if(lim <= l) {
		return &buffer[0];
	}
	__int128 mid = (l + r) / 2;
	Node *cur = &buffer[c++];
	cur->left = build(node->left, l, mid, lim);
	cur->right = build(node->right, mid, r, lim);
	cur->sum = cur->left->sum + cur->right->sum;
	return cur;
}


long long count_tastiness(long long x, std::vector<long long> a) {
	buffer[0].left = buffer[0].right = &buffer[0];
	buffer[0].sum = 0;
	c = 1;
	buffer[1].left = buffer[1].right = &buffer[0];
	buffer[1].sum = 1;
	c = 2;
	for(int i = 0; i < 64; i++) {
		a.push_back(0);
	}

	Node* root = &buffer[1];
	__int128 sum = 0;
	for(int i = 0; i < (int) a.size(); i++) {
		sum += ((__int128) a[i]) << i;
		// sum <= (y + pot) * x
		// floor(sum / x) <= y + pot
		// floor(sum / x) - pot <= y
		Node* cur = &buffer[c++];
		cur->left = root;
		__int128 pot = (__int128) 1 << i;
		cur->right = build(root, 0, pot, sum / x - pot + 1);
		cur->sum = cur->left->sum + cur->right->sum;
		root = cur;
		//std::cout << "after i " << i << " got ans " << root->sum << " lim was " << (long long) (sum / x - pot + 1) << '\n';
	}
	return root->sum;
}

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