Submission #1025048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025048		TheWilp	Packing Biscuits (IOI20_biscuits)	C++14	12 / 100	5 ms	1884 KiB

biscuits

#include "biscuits.h"
#include <algorithm>
#include <queue>
#include <iostream>

using ll = long long;

std::vector<ll> dp;
std::vector<ll> sumdp;
std::vector<ll> ori_v;

ll func(std::vector<ll> s,ll x) {
	if(s.size() == 0) return 1;
	if(s.size() == 1) return s[0] >= x ? 2 : 1;
	if((s.back() == ori_v[s.size() - 1] || s.back() >= x) && s.back() != 0){
		return sumdp[s.size() - 1];
	}
	else {
		ll cumsum = 0;
		for(int q = 0;q < s.size();q++) {
			cumsum += s[q] << q;
		}
		if(cumsum >= x << (s.size() - 1)) {
			std::vector<ll> v(s.begin(),s.end());
			ll require = x - v.back();
			v.pop_back();
			int i = v.size() - 1;
			while(require > 0) {
				require *= 2;
				if(require > v[i]) {
					require -= v[i];
					v[i] = 0;
				}
				else {
					v[i] -= require;
					require = 0;
				}
				--i;
			}
			return func(v,x) + sumdp[v.size() - 1];
		}
		else {
			s.pop_back();
			return func(s,x);
		}
	}
}

long long count_tastiness(long long x, std::vector<long long> a) {
	dp.clear();
	sumdp.clear();
	ori_v.clear();
	std::vector<ll> v;
	ll c = 0;
	ll i = 0;
	while(true) {
		c /= 2;
		if(i < a.size()) c += a[i++];
		if(c >= x) {
			v.push_back(x);
			c -= x;
		}
		else {
			v.push_back(c);
			c = 0;
		}
		if(c % 2 == 1) {
			v.back()++; c--;
		}
		if(i == a.size() && c == 0) break;
	}
	v.push_back(0);
	ori_v = v;

	dp.push_back(v[0] >= x ? 2 : 1);
	sumdp.push_back(dp[0]);
	ll cum_sum = v[0];
	for(int q = 1;q < v.size();q++) {
		ll local = 0;
		cum_sum += v[q] << q;
		if(cum_sum >= x << q) {
			ll require = x - v[q];
			std::vector<ll> s(v.begin(),v.begin() + q);
			int i = s.size() - 1;
			while(require > 0) {
				require *= 2;
				if(require > s[i]) {
					require -= s[i];
					s[i] = 0;
				}
				else {
					s[i] -= require;
					require = 0;
				}
				--i;
			}
			local += func(s,x);
		}
		dp.push_back(local);
		sumdp.push_back(dp.back() + sumdp.back());
	}
	return sumdp.back();
}


// ll func(std::vector<ll>& s,ll x) {
// 	if(s.size() == 0) return 1;
// 	if(s.size() == 1) return s[0] >= x ? 2 : 1;
// 	if(s.back() == 0 && s[s.size() - 2] > 0) {
// 		if(s[s.size() - 2] > x - 1){

// 		}
// 		else {
// 			s.pop_back();
// 			return 
// 		}
// 	}
// 	else if(s.back() > 0) {
// 		std::vector<ll> v(s.begin(),s.end());
// 		ll cumsum = 0;
// 		for(int q = 0;q < v.size();q++) {
// 			cumsum += v[q] << q;
// 		}
// 		if(cumsum >= x << (v.size() - 1)) {
// 			ll require = x - v.back();
// 			v.pop_back();
// 			int i = v.size() - 1;
// 			while(require > 0) {
// 				require *= 2;
// 				if(require > v[i]) {
// 					require -= v[i];
// 					v[i] = 0;
// 				}
// 				else {
// 					v[i] -= require;
// 					require = 0;
// 				}
// 				--i;
// 			}
// 			return func(v,x) + sumdp[v.size() - 1];
// 		}
// 		else {
// 			s.pop_back();
// 			return func(s,x);
// 		}
// 	}
// 	else {
// 		s.pop_back();
// 		return(func(s,x));
// 	}
// }

Compilation message (stderr)

biscuits.cpp: In function 'll func(std::vector<long long int>, ll)':
biscuits.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for(int q = 0;q < s.size();q++) {
      |                 ~~^~~~~~~~~~
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:58:8: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   if(i < a.size()) c += a[i++];
      |      ~~^~~~~~~~~~
biscuits.cpp:70:8: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   if(i == a.size() && c == 0) break;
      |      ~~^~~~~~~~~~~
biscuits.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int q = 1;q < v.size();q++) {
      |                ~~^~~~~~~~~~

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